题解：P4351 [CERC2015] Frightful Formula

· · 题解

题意，即给定 F(1,i),F(i,1)，定义 F(i,j)=aF(i,j-1)+bF(i-1,j)+c\ (i,j\in [2,n])，求 F(n,n)。

考虑将其转化为网格图计数问题，定义向下走的权值为 b，向右走的权值为 a，一条路径的权值为各步权值之积。将所有 (i,2) 和 (2,i) 到 (n,n) 的路径权值分别乘上 F(i,1),F(1,i) 求和，就得到了答案的一部分。

考虑剩下的部分，也就是 c 乘上一些东西。显然这一部分就是所有满足 i,j\in [2,n] 的 (i,j)\rightarrow (n,n) 的路径权值乘上 c 的和。

将两部分求和即可得到答案：

\sum_{i=2}^n {2n-i-2\choose n-2}a^{n-2}b^{n-i}F(i,1)+ \sum_{i=2}^n {2n-i-2\choose n-2}b^{n-2}a^{n-i}F(1,i)+ c\sum_{i=0}^{n-2}\sum_{j=0}^{n-2}{i+j\choose j}a^ib^j

根据经典结论 \sum_{i=0}^n{i+m\choose i}={m+n+1\choose n} 容易求出第一部分的值。考虑第二部分：

c\sum_{i=0}^{n-2}\sum_{j=0}^{n-2}{i+j\choose j}a^ib^j

枚举 i，那么剩下要求的就是 f_i=\sum_{j=0}^{n-2}{i+j\choose j}b^j，答案即为 c\sum_{i=0}^{n-2}f_ia^i。f_0 是好求的，考虑通过 f_i 求出 f_{i+1}，由组合数基本性质易得：

f_{i+1}=\sum_{j=0}^{n-2}\left({i+j\choose j}+[j>0]{i+1+j-1\choose j-1}\right)b^j=f_i+bf_{i+1}-{i+n-1\choose n-2}b^{n-1}

解得：

f_{i+1}=\frac{{i+n-1\choose n-2}b^{n-1}-f_i}{b-1}

特判一下 b=1，然后就做完了，时间复杂度 \mathcal O(n)。

参考代码：

#include<bits/stdc++.h>
#define ll long long
#define mxn 400003
#define md 1000003
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rept(i,a,b) for(int i=(a);i<(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int n;
ll a,b,c,xi,ans,f[mxn],d1[mxn],d2[mxn],p1[mxn],p2[mxn],fac[mxn],ifac[mxn];
ll power(ll x,int y){
    ll ans=1;
    for(;y;y>>=1){
        if(y&1)ans=ans*x%md;
        x=x*x%md;
    }
    return ans;
}
inline ll C(int n,int m){
    if(m>n||m<0)return 0;
    return fac[n]*ifac[m]%md*ifac[n-m]%md;
}
void init(int n){
    fac[0]=1;
    rep(i,1,n)fac[i]=fac[i-1]*i%md;
    ifac[n]=power(fac[n],md-2);
    drep(i,n,1)ifac[i-1]=ifac[i]*i%md;
}
signed main(){
    scanf("%d%lld%lld%lld",&n,&a,&b,&c),xi=power(b-1,md-2);
    p1[0]=p2[0]=1;
    rep(i,1,n){
        p1[i]=p1[i-1]*a%md;
        p2[i]=p2[i-1]*b%md;
    }
    init(n<<1);
    rep(i,1,n)scanf("%lld",&d1[i]);
    rep(i,1,n)scanf("%lld",&d2[i]);
    rep(i,2,n){
        ans=(ans+C(n*2-i-2,n-2)*p1[n-1]%md*p2[n-i]%md*d1[i])%md;
        ans=(ans+C(n*2-i-2,n-2)*p2[n-1]%md*p1[n-i]%md*d2[i])%md;
    }
    if(b==1){
        rep(i,0,n-2)ans=(ans+c*p1[i]%md*C(i+n-1,i+1))%md;
    }else{
        rep(i,0,n-2)f[0]=(f[0]+p2[i])%md;
        rept(i,0,n-2)f[i+1]=(C(i+n-1,n-2)*p2[n-1]-f[i])%md*xi%md;
        rep(i,0,n-2)ans=(ans+c*p1[i]%md*f[i])%md;
    }
    cout<<ans;
    return 0;
}