P4351 [CERC2015]Frightful Formula

· · 题解

思路和楼下 srz 的差不多，但是加了一点自己思考中的细节补充（

答案可以有以下三个部分组成：第一行对答案做的贡献；第一列对答案做的贡献；c 对答案做的贡献。考虑第一行 (1,k) 对答案做的贡献，组合意义为从 (1,k) 走到 (n,n)，向右走贡献为 a，向下走贡献为 b 贡献总和。由于 (1,k) 只能走到 (2,k)，所以实际上真正可以开始自由走的出发点是 (2,k)。所以 (1,k) 的贡献为：

\binom{2n-2-k}{n-2}a^{n-k}b^{n-1}f_{1,k}

同理，(k,1) 的贡献为：

\binom{2n-2-k}{n-2}a^{n-1}b^{n-k}f_{k,1}

考虑能不能消掉 c 的贡献。找到一个 x=\frac{c}{1-a-b} 满足 x=ax+bx+c，可以转化成 f_{i,j}-c=a(f_{i,j-1}-x)+b(f_{i-1,j}-x)。设 g=f-x，则我们可以直接求出 g_{n,n} 即可。

不过如果没有 x，即 a+b\equiv 1 呢？我们带入。f_{i,j}=a\cdot f_{i,j-1}+(1-a)\cdot f_{i-1,j}+c。我们希望求出一个 y，满足：

f_{i,j}-y_{i,j}=a\cdot (f_{i,j-1}-y_{i,j-1})+(1-a)\cdot (f_{i-1,j}-y_{i,j-1})

即

c-y_{i,j}=-a\cdot y_{i,j-1}+a\cdot y_{i,j-1}-y_{i,j-1}

为了消去 a，我们需要 y_{i,j-1}=y_{i-1,j}。那么 y 应该是一个关于 (i+j) 的式子（因为两个东西的下标和相等）。设 y=k(i+j)。解方程可以得到 k=c。于是，我们有 g_{i,j}=f_{i,j}-c(i+j)。我们求出 g_{n,n} 即可。

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=4e5+9,mod=1e6+3;

inline long long read() {
    register long long x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int n,a,b,c,l[N],t[N],pwa[N],pwb[N],fac[N],inv[N],ifac[N];
void pre(int n) {
    inv[0]=inv[1]=fac[0]=ifac[0]=pwa[0]=pwb[0]=1;
    rep(i,1,n) fac[i]=fac[i-1]*i%mod;
    rep(i,2,n) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    rep(i,1,n) ifac[i]=ifac[i-1]*inv[i]%mod;
    rep(i,1,n) pwa[i]=pwa[i-1]*a%mod;
    rep(i,1,n) pwb[i]=pwb[i-1]*b%mod;
}
int C(int x,int y) {
    if(x<0||y<0||x<y) return 0;
    else return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
int ksm(int x,int y,int ret=1) {
    while(y) {
        if(y%2) ret=ret*x%mod;
        x=x*x%mod, y>>=1;
    }
    return ret;
}

signed main() {
    n=read(), a=read(), b=read(), c=read();
    rep(i,1,n) l[i]=read();
    rep(i,1,n) t[i]=read();
    pre(2*n);
    if((a+b)%mod!=1) {
        int x=c*ksm((1+mod+mod-a-b)%mod,mod-2)%mod,ans=0;
        rep(i,2,n) ans=(ans+C(2*n-2-i,n-2)*pwa[n-i]*pwb[n-1]%mod*(t[i]-x))%mod;
        rep(i,2,n) ans=(ans+C(2*n-2-i,n-2)*pwa[n-1]*pwb[n-i]%mod*(l[i]-x))%mod;
        ans=(ans+x+mod)%mod;
        printf("%lld\n",ans);
    } else {
        int ans=0;
        rep(i,2,n) {
            int x=c*(1+i)%mod;
            ans=(ans+C(2*n-2-i,n-2)*pwa[n-i]*pwb[n-1]%mod*(t[i]-x))%mod;
            ans=(ans+C(2*n-2-i,n-2)*pwa[n-1]*pwb[n-i]%mod*(l[i]-x))%mod;
        }
        ans=(ans+2*c*n+mod)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}