f1,i 的贡献是 f1,i∗an−i∗bn−1∗Cn−i2n−i−2 fi,1 同理 注意 f1,1 没什么卵用 然后 c 还有贡献 c∑i=2n∑j=2nan−i∗bn−j∗Cn−i2n−i−j=c∑i=0n−2∑j=0n−2ai∗bj∗Cii j 写成卷积的形式然后FFT就好了
正解似乎是递推
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int P=1e6+3; const int M[]={998244353,1004535809,469762049}; const int G[]={3,3,3}; const ll _M=(ll)M[0]*M[1]; inline ll Pow(ll a,int b,int p){ ll ret=1; for (;b;b>>=1,a=a*a%p) if (b&1) ret=ret*a%p; return ret; } inline ll mul(ll a,ll b,ll p){ a%=p; b%=p; return ((a*b-(ll)((ll)((long double)a/p*b+1e-3)*p))%p+p)%p; } const int m1=M[0],m2=M[1],m3=M[2]; const int inv1=Pow(m1%m2,m2-2,m2),inv2=Pow(m2%m1,m1-2,m1),inv12=Pow(_M%m3,m3-2,m3); inline int CRT(int a1,int a2,int a3){ ll A=(mul((ll)a1*m2%_M,inv2,_M)+mul((ll)a2*m1%_M,inv1,_M))%_M; ll k=((ll)a3+m3-A%m3)*inv12%m3; return (k*(_M%P)+A)%P; } const int N=600005; int n,A,B,C; ll ans; #define read(x) scanf("%d",&(x)) ll fac[N],inv[N]; inline void Pre(int n){ fac[0]=1; for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%P; inv[1]=1; for (int i=2;i<=n;i++) inv[i]=(ll)(P-P/i)*inv[P%i]%P; inv[0]=1; for (int i=1;i<=n;i++) inv[i]=inv[i]*inv[i-1]%P; } inline ll _C(int n,int m){ return fac[n]*inv[m]%P*inv[n-m]%P; } int m; int R[N]; struct NTT{ int P,G; int num,w[2][N]; int R[N]; void Pre(int _P,int _G,int m){ num=m; P=_P; G=_G; int g=Pow(G,(P-1)/num,P); w[1][0]=1; for (int i=1;i<num;i++) w[1][i]=(ll)w[1][i-1]*g%P; w[0][0]=1; for (int i=1;i<num;i++) w[0][i]=w[1][num-i]; int L=0; while (m>>=1) L++; for (int i=1;i<=num;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1)); } void FFT(int *a,int n,int r){ for (int i=0;i<n;i++) if (i<R[i]) swap(a[i],a[R[i]]); for (int i=1;i<n;i<<=1) for (int j=0;j<n;j+=(i<<1)) for (int k=0;k<i;k++){ int x=a[j+k],y=(ll)a[j+i+k]*w[r][num/(i<<1)*k]%P; a[j+k]=(x+y)%P; a[j+i+k]=(x+P-y)%P; } if (!r) for (int i=0,inv=Pow(n,P-2,P);i<n;i++) a[i]=(ll)a[i]*inv%P; } }ntt[3]; int a[N],b[N],c[N],d[N]; int _a[3][N]; int main(){ int x; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(n); read(A); read(B); read(C); Pre(2*n); for (int i=1;i<=n;i++) read(x),ans+=(i>1)*(ll)x*Pow(A,n-1,P)%P*Pow(B,n-i,P)%P*_C(2*n-i-2,n-i)%P; for (int i=1;i<=n;i++) read(x),ans+=(i>1)*(ll)x*Pow(A,n-i,P)%P*Pow(B,n-1,P)%P*_C(2*n-i-2,n-i)%P; ans%=P; int L=0; m=1; while (m<=(2*n-4)) m<<=1,L++; for (int i=1;i<m;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1)); for (int i=0;i<=n-2;i++) a[i]=Pow(A,i,P)*inv[i]%P,b[i]=Pow(B,i,P)*inv[i]%P; for (int i=0;i<3;i++){ ntt[i].Pre(M[i],G[i],m); memcpy(c,a,sizeof(int)*(m+5)); memcpy(d,b,sizeof(int)*(m+5)); ntt[i].FFT(c,m,1); ntt[i].FFT(d,m,1); for (int j=0;j<m;j++) c[j]=(ll)c[j]*d[j]%ntt[i].P; ntt[i].FFT(c,m,0); for (int j=0;j<m;j++) _a[i][j]=c[j]; } ll ret=0; for (int i=0;i<=2*n-4;i++) ret+=fac[i]*CRT(_a[0][i],_a[1][i],_a[2][i])%P; ret=(ret%P)*C%P; ans=(ans+ret)%P; printf("%lld\n",ans); return 0; }