高度由习惯堆积

分类 算法:多项式乘法 下的文章

March 17, 2019

MTT板子

先放个板子。void MTT(LL *A,LL *B,int la,int lb,LL *C){ int mm=la+lb,nn,c=0; for(nn=1;nn<mm;nn<<=1)c++; for(int i=0;i<nn;i++){ rev[i]=(rev[i>>1]>>1)|((i&1)&...

HDU6061 RXD and functions

题目题目链接思路显然可以发现,那些a其实和最终的结果没有关系,我们关心的仅仅是所有a的总和,设这个和为$a$。也就是说$g(x)=f(x-a)$通过二项式定理展开得:$\sum_{i=0}^{n}c_i \sum_{j=0}^{i} \binom{i}{j} (-a)^{i-j}x^{j}$因为要求的是$x^j$的系数,所以整理一下,把$j$写在前面。$$ \sum_{j=0}^{n}\su...

BZOJ3527 力

题目给出n个数qi,给出Fj的定义如下:令Ei=Fi/qi,求Ei.思路年轻人的第一道FFT。$$ E_j=\sum_{i<j}\frac{q_i}{(i-j)^2}-\sum_{i>j}\frac{q_i}{(i-j)^2} $$设:$$ f[i]=q_i\\ g[i]=\frac{1}{i^2} $$那么原式可以化为:$$ E_j=\sum_{i<j}f[i]g[j-i...