自动搬运

查看原文

来自洛谷，原作者为

	CYJian 今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました

搬运于2025-08-24 22:08:25，当前版本为作者最后更新于2019-02-14 21:41:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Candies

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

15分做法

枚举。。不多BB..

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

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

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

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

然后就可以拿到$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)$

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