傳送門:洛谷

前題提要:包含了簡單的生成函數(shù)思想以及多項式乘法,是一道不可多得的多項式好題.故記錄一下.

題意:給定一個長為 n 的序列 a，求出其 k 階差分或前綴和。結(jié)果的每一項都需要對 1004535809取模。

對于差分和前綴和我們分開來討論.

先討論前綴和部分:

先列出$A$序列:$(a_1,a_2,...,a_n)$,再列出前綴和$S$序列:$(s_1,s_2,...,s_n)$,為了等會的方便起見,我們將這兩個序列擴展一下,分別加上一個$a_0,s_0$.(并且這兩個值規(guī)定為0)
存在$s_0=0,s_1=a_0+a_1,s_n=a_0+a_1+...+a_n$
我們將其往多項式那邊靠,不難發(fā)現(xiàn),如果存在另一個序列$B$為$(1,1,\mathrm{1...1})$,那么此時我們的$S=A?B$,也就是$S$序列是$A$與$B$的卷積系數(shù)結(jié)果.
所以一階前綴和$S1=A1?B1$,那么二階$S2=S1?B1$,因為多項式卷積滿足結(jié)合律$k$階即為$Sk=S1?B{1}^k$.
此時如果多項式的科技比較強,直接套一個多項式快速冪就結(jié)束了.
但是顯然我的科技樹比較差,所以來討論一下低科技的解法
因為我們無法進(jìn)行多項式快速冪,所以我們考慮使用生成函數(shù)的方法將多項式轉(zhuǎn)為一個函數(shù)然后在做考慮.那么此時我們的$B$就是$1+x+x^2+...+x^n$,求一下和就是$(1?x^n)/(1?x)$,為了方便起見,我們此時不妨選擇$x\in (0,1)$,那么此時我們的$B$就是$1/(1?x)$,那么此時$B^k=(1?x{)}^{?k}$.
考慮使用擴展二項式定理:$$(a+b{)}^n=a^n?(1+\frac{b}{a}{)}^n=a^n?\sum _{i=0}^{\infty }\left(\genfrac{}{}{0ex}{}{n}{i}\right)?(\frac{b}{a}{)}^i$$
那么對于上述式子來說就是$$B^k=\sum _{i=0}^{\infty }\left(\genfrac{}{}{0ex}{}{?k}{i}\right)?(?1{)}^i?x^i$$$${\left(\genfrac{}{}{0ex}{}{?k}{i}\right)}^{=}\frac{(?k)?(?k?1)?(?k?2)?...?(?k?i+1)}{i!}$$$$=(?1{)}^i?\frac{k?(k+1)?(k+2)?...(k+i?1)}{i!}$$$$=(?1{)}^i?C_{k+i?1}^i$$

對于$C_{k+i?1}^i$,顯然我們是遞推來求和的(注意本題的$k$很大,只能遞推來求和,無法預(yù)處理),$C_{k+i?1}^i=C_{k+i?2}^{i?1}?(\frac{k+i?1}{i})$.

那么此時我們的k階前綴和就到此結(jié)束了,只要使用$NTT$解決一下多項式乘法即可.

下面講一下這道題的k階差分部分.其實大體上的解決方案和前綴和是一樣的.
同樣考慮得出B序列為$(1,?1,0,0,\mathrm{0...0})$ [推導(dǎo)方式和上述一樣,此處就不在贅述了].
使用生成函數(shù)將$B^k$序列轉(zhuǎn)化一下就是$(1?x{)}^k$,使用二項式定理展開就是${\sum }_{i=0}^{\infty }{C}_k^i?(?x{)}^k$,同樣遞推一下即可.

最后也是拿$NTT$做一下多項式乘法即可解決.

下面是具體的代碼部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
inline void print(__int128 x){if(x<0) {putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const int mod=1004535809;
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int f[maxn],g1[maxn],g2[maxn];
inline ll get_read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=(x*10%mod+ch-'0')%mod;return x*w;
}
int qpow(int a,int b) {int ans=1;while(b) {if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;
}
int rev[maxn];
void NTT(int *a,int n,int inv) {for(int i=0;i<=n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);for(int len=1;len<=(n>>1);len<<=1) {int gn=qpow(inv==1?3:qpow(3,mod-2),(mod-1)/(len<<1));for(int i=0;i<=n;i+=(len<<1)) {int g0=1;for(int j=0;j<=len-1;j++) {int x=a[i+j],y=a[i+j+len]*g0%mod;a[i+j]=(x+y)%mod;a[i+j+len]=((x-y)%mod+mod)%mod;g0=g0*gn%mod;}}}
}
signed main() {int n=read();int k=get_read();int t=read();for(int i=1;i<=n;i++) {f[i]=read();}int limit=1,len=0;while(limit<=2*n) limit<<=1,len++;for(int i=0;i<=limit;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));g1[0]=1;for(int i=1;i<=n;i++) {g1[i]=g1[i-1]*(k+i-1)%mod*qpow(i,mod-2)%mod;}g2[0]=1;for(int i=1;i<=n;i++) {g2[i]=(g2[i-1]*(k-i+1)%mod*qpow(i,mod-2)%mod*-1+mod)%mod;}if(t==0) {NTT(f,limit,1);NTT(g1,limit,1);for(int i=0;i<=limit;i++) {f[i]=f[i]*g1[i]%mod;}NTT(f,limit,-1);int inv=qpow(limit,mod-2);for(int i=0;i<=limit;i++) {f[i]=f[i]*inv%mod;}}else {NTT(f,limit,1);NTT(g2,limit,1);for(int i=0;i<=limit;i++) {f[i]=f[i]*g2[i]%mod;}NTT(f,limit,-1);int inv=qpow(limit,mod-2);for(int i=0;i<=limit;i++) {f[i]=f[i]*inv%mod;}}for(int i=1;i<=n;i++) {cout<<f[i]<<" ";}return 0;	
}