CERC2015 Frightful Formula 神奇的模意义下分数

2019-04-13 13:00发布

站内文章 / 模拟电子
17598 0 1438
上网查了下这道题的正解是FFT......然而机智的xushu用待定系数法A了。。。。 f[i,j]+k=a(f[i][j-1]+k)+b(f[i-1,j]+k) 解得 k=c/(a+b-1) 于是令g[i][j]=f[i][j]+k，g[i][j]=a*g[i][j-1]+b*g[i-1][j], 之后再计算g[i][1] 和 g[1][j]对 g[n][n]的贡献，就是从g[i][1]走到g[i][2]后，再走到g[n][n]有多少条路径，直接组合数，然后向右走是乘上一个a，向下走是乘上一个b，就可以很快计算出g[n][n]了，最后f[n][n]=g[n][n]-k。哇，好机智啊。 今天问了一下xushu，关于那个模意义下的分数，是真的可以表示出来的 就是a%mod不等于(a+2/7)%mod，很神奇，以后有时间要研究一下数论。 #include #include #define maxl 200010 #define mod 1000003 long long n,A,B,C,ans; long long fi[maxl],fj[maxl]; long long powa[maxl],powb[maxl],c[maxl]; void prework() { scanf("%lld",&n); scanf("%lld%lld%lld",&A,&B,&C); for(long long i=1;i<=n;i++) scanf("%lld",&fi[i]); for(long long i=1;i<=n;i++) scanf("%lld",&fj[i]); powa[0]=1;powb[0]=1; for(long long i=1;i<=n;i++) powa[i]=(powa[i-1]*A)%mod, powb[i]=(powb[i-1]*B)%mod; } long long qp(long long a,long long b) { long long ans=1,cnt=a; while(b) { if(b&1) ans=(ans*cnt)%mod; cnt=(cnt*cnt)%mod; b>>=1; } return ans; } void mainwork() { if(A==0 && B==0) {ans=C;return;} if(A==1 && B==0) { ans=fi[n]; for(long long i=2;i<=n;i++) ans=(ans*A+C)%mod; return; } if(A==0 && B==1) { ans=fj[n]; for(long long j=2;j<=n;j++) ans=(ans*B+C)%mod; return; } c[n]=1;long long zi=1,mu=1,d=1,d1,d2; for(long long i=n-1;i>=2;i--) { zi=(zi*(n+d-2))%mod;mu=(mu*d)%mod; c[i]=(zi*qp(mu,mod-2))%mod;d++; } for(long long i=2;i<=n;i++) { d1=((c[i]*powa[n-1])%mod*powb[n-i])%mod; d2=((c[i]*powb[n-1])%mod*powa[n-i])%mod; ans=(ans+d1*fi[i]+d2*fj[i])%mod; ans=(ans+(((d1+d2)*C)%mod*qp(A+B-1,mod-2))%mod)%mod; } ans=(ans-(C*qp(A+B-1,mod-2))%mod)%mod; ans=(ans+mod)%mod; } void print() { printf("%lld",ans); } int main() { prework(); mainwork(); print(); return 0; }


热门文章