ACM一道动态规划题

发布网友发布时间：2022-04-29 22:24

共1个回答

热心网友时间：2022-06-24 12:11

不知道K有多大，如果k比较小的话,可以这样做；
1、开个conut数组，初始化为0
2、叠加求出第一个数到第j(1<=j<=ai)个数的和模上k，如果得到i，那么count[i]++; O(ai)复杂度
3、最后对每个count[i],求组合数C(count[i]，2) ，把这些结果加起来，在加上count[0]就行了
总的复杂度为O(ai+k)；
解释：如果第1~X的和与第1~Y的和模k相等，那么第X+1~Y的和就为k的倍数，最后因为
count[0]，每个和本身就是K的倍数，所以在加上count[0]。

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com