题解 P5224 【Candies】

· · 题解

Candies

相信大佬都做过这道题，Candies这道题是我在学长讲完那一道数据比较弱的题目yy出来的优化做法。(如果是任意模数就需要MTT了。。)

15分做法

枚举。。不多BB..

15分做法（看起来强一点的做法）

还是上面那一道题的做法吧。。

我们可以设状态f[i][j]表示从i箱糖中选择箱数为\% k \equiv j的方案数，然后考虑加入一箱会有什么影响：

显然是加入的这一箱可以选，也可以不选。所以我们有转移：

f[i][j] = f[i-1][j] + f[i-1][(j-1+k)\%k]

然后就可以拿到15分的高分。。

40分做法

发现k还是比较小，考虑矩阵快速幂。

然后就可以构造出一个k \ast k的矩阵，然后就可以O(k^3logN)做了。。

60分做法(优化1)

这个时候k变大了，考虑优化。

发现构造的矩阵是一个循环矩阵(此题中为下一行为上一行向右转1得到)

然后就可以考虑每一次做矩阵乘法只需要用第一行乘就行了。因为其他行的答案都可以用旋转得到。

这样复杂度就是O(k^2 \ast logN)

60分做法(优化2)

考虑合并x箱的答案f[x]和y箱的答案f[y]

发现可以有一个暴力转移：

f[x+y][(i + j) \% k] = \sum f[x][i] \ast f[y][j]

简单的乘法原理应该没有问题吧。。

然后就发现可以倍增，这样就预处理出每一个二进制位的f[x]，然后根据N的二进制位合并答案就好了。

复杂度O(k^2 \ast logN)

100分做法

发现上面的优化2是一个卷积的形式，所以可以NTT优化。只不过卷积乘出来超出k的部分需要把多的部分弄进k的范围内。简单来说，就是f[i](i>k)就要加到f[i\%k]里面。

发现题目非常友好没有要写MTT，给出的模数的原根就是3.

复杂度O(k \ast logk \ast logN)

代码太丑了，就不放了。。