Luogu

Gym

分析

先考虑 $c=0$ 的情况。我们计算每个 $l_i$ 和 $t_i$ 对 $(n,n)$ 的贡献。

只考虑 $l_i$,那么相当于从 $(i,1)$ 走到 $(n,n)$,第一步必须往右,往右走一步乘 $a$,往下走一步乘 $b$,求所有路径的权值和。这个东西显然等于

$$ {2n-i-2\choose n-2}a^{n-1}b^{n-i} $$

再考虑 $c$ 的贡献。同理可以知道,$(x,y)$ 对 $(n,n)$ 的贡献是

$$ c{2n-x-y\choose n-x}a^{n-y}b^{n-x} $$

那么总贡献是

$$ \begin{aligned} &c\sum_{i=2}^n\sum_{j=2}^n{2n-i-j\choose n-i}a^{n-j}b^{n-i}\\ =&c\sum_{i=2}^n\sum_{j=2}^n(2n-i-j)!\frac{a^{n-j}}{(n-j)!}\frac{b^{n-i}}{(n-i)!}\\ =&c\sum_{d=4}^{2n}(2n-d)!\sum_{i+j=d}\frac{a^{n-j}}{(n-j)!}\frac{b^{n-i}}{(n-i)!} \end{aligned} $$

后面是卷积的形式,于是直接 MTT 即可。

有的小青年就发问了,我不喜欢卷积,我不喜欢 MTT,我永远只爱组合意义,你这种推式子,我很不满意!

很好!很有精神!那我们就来分析一下。

我们打个表看一下每一项对 $(n,n)$ 的贡献

$$ \begin{matrix} ca^0b^0{0+0\choose 0} & ca^1b^0{1+0\choose 1} & ca^2b^0{2+0\choose 2} & \cdots \\ ca^0b^1{0+1\choose 0} & ca^1b^1{1+1\choose 1} & ca^2b^1{2+1\choose 2} & \cdots \\ ca^0b^2{0+2\choose 0} & ca^1b^2{1+2\choose 1} & ca^2b^2{2+2\choose 2} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{matrix} $$

可以发现,当 $i+j\leq n-2$ 时,贡献就是 $c(a+b)^{i+j}$;当 $i+j>n-2$ 时,可以把上一 / 的贡献乘上 $a+b$,然后再减去边上两项,就可以得到贡献了。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;
const int mod=1e6+3;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,a,b,c,l[N],t[N],fac[N],ifac[N],pwa[N],pwb[N];
int C(int n,int m) { return 1ll*fac[n]*ifac[m]*ifac[n-m]%mod; }
void init(int n) {
    fac[0]=1;
    for (int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for (int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
    for (int i=pwa[0]=1;i<=n;++i) pwa[i]=1ll*pwa[i-1]*a%mod;
    for (int i=pwb[0]=1;i<=n;++i) pwb[i]=1ll*pwb[i-1]*b%mod;
}

int main() {
    n=read(),a=read(),b=read(),c=read(); init(n<<1);
    for (int i=1;i<=n;++i) l[i]=read();
    for (int i=1;i<=n;++i) t[i]=read();
    int ans=0;
    for (int i=2;i<=n;++i) ans=(ans+1ll*l[i]*C(n-i+n-2,n-2)*pwa[n-1]%mod*pwb[n-i])%mod;
    for (int i=2;i<=n;++i) ans=(ans+1ll*t[i]*C(n-i+n-2,n-2)*pwa[n-i]%mod*pwb[n-1])%mod;
    int s=1; ans=(ans+c)%mod;
    for (int i=1;i<=n-2;++i) s=1ll*s*(a+b)%mod,ans=(ans+1ll*c*s)%mod;
    for (int i=0;i<=n-3;++i) {
        s=1ll*s*(a+b)%mod;
        s=(s-(1ll*pwa[i]*pwb[n-1]+1ll*pwa[n-1]*pwb[i])*C(n-2+i,i)%mod+mod)%mod;
        ans=(ans+1ll*c*s)%mod;
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2020 年 11 月 12 日 10 : 25 PM