多项式取模与线性递推优化

2019-04-13 16:52发布

站内文章 / 模拟电子
15677 0 1368
       最近51nod比赛最后一题，我列出母函数以后发现要求m<=10^16项系数，于是现在来写一下这个问题。        假设f(x)=f(x)*g(x)+1。        经过询问黈力，大致明白了多项式取模解决线性递推式的方法。实际上，若g(x)次数为n，那么可以看成x^(n+1)=g(x)的一个方程，然后求x^m的值的问题，那么这相当于多项式快速幂，直接用多项式取模解决即可。        一下是一个另类的做法。（不保证正确）       （根据感性理解），对于任意一个数p，f(x)关于f(x-p),f(x-p-1),...,f(x-p-n)的转移应该都是一样的。考虑f(x)的x^k项系数，实际上可以看成x^t->x^(k+t)的一个转移（可以将<0的项看成是0）。那么考虑现在已经求出了x^(2^i)~2^(2^i+2*n)的答案，再对x^(2^i)~(x^2^i+n)做一个卷积，就可以求出x^(2^(i+1))~(x^(2^(i+1))+n)项的答案，然后考虑通过前n项求出它接下来的n项。设前n项为q(x)，新的若干项为t(x)，那么首先求出q(x)*g(x)的>n的多项式，然后/x^n，设得到的r(x)，那么就有：         t(x)=t(x)*g(x)+r(x)        那么可以预处理(1-g(x))^(-1)，然后与r(x)卷积后模x^n，得到t(x)        这样就可以预处理x^(2^i)~x^(2^i+n)的系数，同样就可以得到x^m了。        考虑到实现难度。。并不推荐这种做法。         

热门文章