P5488 差分与前缀和 题解
题面
推式子+二项式定理+FFT。这个题需要一点生成函数的知识。
首先考虑前缀和，求一个多项式 \(F(x)\) 的前缀和相当于是卷上了一个系数全是 \(1\) 的多项式。即
\[\begin{aligned} Sum(x)&=F(x)\times \sum_{i=0}^{\infty}x^i\\ &=F(x)\times \frac{1}{1-x} \end{aligned} \]那么 \(k\) 阶前缀和即
\[\begin{aligned} Sum(x)&=F(x)\times \frac1{(1-x)^k}\\ &=F(x)\times (1-x)^{-k}\\ &=F(x)\times \sum_{i=0}^{\infty}\binom{k+i-1}{i-1}x^i \end{aligned} \]使用FFT/NTT优化即可。
考虑到差分是前缀和的逆运算，则
\[\begin{aligned} Dif(x)&=F(x)\times (1-x)^k\\ &=F(x)\times \sum_{i=0}^{\infty}(-1)^i\binom{k-i+1}{i}x^i \end{aligned} \]同样的道理，直接FTT/NTT即可。
点击查看代码
#include
#include
using namespace std;
const int N=4e5+13,P=1004535809,G=3;
inline int qpow(int a,int k){int s=1;for(;k;k>>=1,a=1ll*a*a%P)if(k&1)s=1ll*s*a%P;return s;}
inline int Inv(int a){return qpow(a,P-2);}
const int Gi=Inv(G);
inline int rd(){
long long res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=((res<<1)+(res<<3)+(c-'0'))%P;
return res;
}
int n,k,op,r[N],a[N],b[N];
inline void fft(int *f,int type,int limit){
for(int i=0;i>1]>>1)|((i&1)<<(l-1));
fft(a,1,limit),fft(b,1,limit);
for(int i=0;i