HDU6061 RXD and functions

题目链接

题意

​ 已知 f(x)=∑ni=0cixi ，给定一个长度为 m 的数列 A ，求 f(x−∑mi=1ai) 的所有系数模998244353的结果。

分析

​ 赛时纠结其它题去了，没有认真推=-=。（虽然推出来了，当时也没有NTT的板子的说）

​ 以下均用 a 代替 ∑mi=1ai

​ 将所有的 (x−a)i 均拆开，并将对应 xi 的系数划分到一块，得到

​

f(x−a)=∑i=0nxi(∑j=incjCijaj−i)

​ 再将组合数部分拆开得到

​

∑i=0nxi(∑j=incjj!(j−i)!i!aj−i)

​ 为了便于计算，将 j 用 j i 进行替换，得到

​

∑i=0nxi(∑j=0n−icj+i(j+i)!j!i!aj)

​ 将内层求和中无关的变量i的部分提出，并进行简单的划分得到

​

∑i=0nxii!(∑j=0n−i(cj+i(j+i)!)(ajj!))

​ 向卷积式凑一下，令 k=n−i−j ，再进行一次替换得到

​

∑i=0nxii!(∑j+k=n−i(cn−k(n−k)!)(ajj!))

​ 将 cn−k(n−k)! 在n长度进行一个翻转就能将式子转换成卷积式，再就是套一下NTT即可，具体可以看代码。

代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define Mp(x,y) make_pair(x,y) #define LL long long #define MAXN 100100 const int inf = 0x3fffffff; const int mmax = 1<<18; const int mod = 998244353; const int g = 3; //原根 LL quick_mod(LL a,LL b){ LL ans=1; for(;b;b/=2){ if(b&1) ans=ans*a%mod; a=a*a%mod; } return ans; } int rev(int x,int r) //蝴蝶操作 { int ans=0; for(int i=0; i<r; i++){ if(x&(1<<i)){ ans+=1<<(r-i-1); } } return ans; } void NTT(int n,LL A[],int on) // 长度为N (2的次数) { int r=0; for(;; r++){ if((1<<r)==n) break; } for(int i=0; i<n; i++){ int tmp=rev(i,r); if(i<tmp) swap(A[i],A[tmp]); } for(int s=1; s<=r; s++){ int m=1<<s; LL wn=quick_mod(g,(mod-1)/m); for(int k=0; k<n; k+=m){ LL w=1; for(int j=0; j<m/2; j++){ LL t,u; t=w*(A[k+j+m/2]%mod)%mod; u=A[k+j]%mod; A[k+j]=(u+t)%mod; A[k+j+m/2]=((u-t)%mod+mod)%mod; w=w*wn%mod; } } } if(on==-1){ for(int i=1;i<n/2;i++) swap(A[i],A[n-i]); LL inv=quick_mod(n,mod-2); for(int i=0;i<n;i++) A[i]=A[i]%mod*inv%mod; } } LL A[mmax+10],B[mmax+10]; LL ans[mmax+10]; int c[MAXN]; LL fac[MAXN]; LL ni[MAXN]; void init(){ fac[0]=ni[0]=1; for(int i=1;i<MAXN;++i) fac[i]=(fac[i-1]*i)%mod; ni[MAXN-1]=quick_mod(fac[MAXN-1],mod-2); for(int i=MAXN-2;i;i--) ni[i]=(ni[i+1]*(i+1))%mod; } int main(){ int n,m,tmp; init(); while(~scanf("%d",&n)){ LL a=0; for(int i=0;i<=n;++i) scanf("%d",&c[i]); scanf("%d",&m); for(int i=0;i<m;++i){ scanf("%d",&tmp); a-=tmp; if(a<0) a+=mod; } if(a==0){ for(int i=0;i<=n;++i) printf("%d ",c[i]); cout<<endl; continue; } B[0]=1; LL aa=1; int l=1; while(l<=2*n) l<<=1; for(int i=0;i<l;++i){ if(i<=n){ A[i]=(fac[n-i]*c[n-i])%mod; B[i]=(aa*ni[i])%mod; } else A[i]=B[i]=0; aa=(aa*a)%mod; } NTT(l,A,1); NTT(l,B,1); for(int i=0; i<l; i++) A[i]=A[i]*B[i]%mod; NTT(l,A,-1); for(int i=0;i<=n;++i) printf("%I64d ",(A[n-i]*ni[i])%mod); cout<<endl; } }