3992: [SDOI2015]序列统计

容易列出dp方程f[i][j]表示第i个位置乘积为j的方案数。
那么推出转移 f[i+1][j*p\%m] += f[i][j]
此时复杂度O(n*m^2) 显然不能接受
想到对于n特别大的情况一般都会用快速幂。
那么可以列出一个m*m的矩阵进行转移,复杂度O(\log n * m^2)
明显还是不能接受,发现瓶颈在于m.
考虑利用fft把 m^2优化掉
如何优化,发现因为j*p\%m导致没法直接递推
那么利用原根g的性质,求出m的原根。
已知g^i互不相同,令i = g[i]
那么原方程可写作f[i+1][g^j*g^p\%m] += f[i][j] \to f[i+1][g^{j+p\%m}] += f[i][j]
那么这样显然可以用fft优化
复杂度O(\log n *\log m*m)
c++代码如下:

 

8 + 4 =