BZOJ 4818 [Sdoi2017] 序列计数

发布于 2018-02-15  136 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4818

题意:Alice 想要得到一个长度为 n 的序列,序列中的数都是不超过 m 的正整数,而且这 n 个数的和是 p 的倍数。Alice 还希望,这 n 个数中,至少有一个数是质数。Alice 想知道,有多少个序列满足她的要求。


好久以前在飞机上脑袋 AC 的一道傻逼题... 由于太困了当时没写就睡觉了... 大年三十随便写一发吧。
至少有一个数是质数即不管这个限制减去没有数是质数的情况。
\(f_{i,j}\) 表示考虑前\(i\) 个数,目前余数是\(j\) 的方案数,\(buc_i\) 表示当前决策一个余数是\(i\) 的数的方案数,转移如下:
\(f_{i,j}=\sum_{k=0}^{p-1}f_{i-1,(j-k)\ mod\ p}\times buc_k\)
发现是一个卷积的形式,由于数据范围非常小不用写 FFT(写了估计会变慢吧...),发现大力转移需要做\(n\) 次,快速幂优化即可。
时间复杂度\(p^2log_n\)。

 


一个非常弱的准退役OIER