[AtCoder ABC154F] Many Many Paths

题目链接

Solution

设 $g(x,y)=\sum\limits_{i=0}^x\sum\limits_{j=0}^y f(i,j)$，即 $f(x,y)$ 的二维前缀和，则答案用二维前缀和的性质加加减减一下即可。问题转化为如何 $O(n)$ 求解 $g(x,y)$.

容易知道的是：$f(x,y)=C_{x+y}^x=\frac{(x+y)!}{x!\cdot y!}$，该式在预处理阶乘后配合逆元 $O(\lg MOD)$ 可求。

我们还需要用到一个性质：$\sum\limits_{i=0}^r f(i,c)=f(0,c)+f(1,c)+\cdots+f(r,c)=f(r,c+1)$，想象走的路线就很容易证明了。

（事实上，上式即 $C_{c}^0+C_{c+1}^1+\cdots+C_{c+r}^r=C_{c+r+1}^{r}$，可反复运用帕斯卡恒等式证明）

于是，$g(x,y)=\sum\limits_{j=0}^y\sum\limits_{i=0}^x f(i,j)=\sum\limits_{j=0}^yf(x,j+1)=\sum\limits_{k=1}^{y+1}f(x,k)$，$O(n)$ 循环即可。

Code

#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 1000005;
const LL MOD = 1e9+7;

LL r1, c1, r2, c2, fac[N<<1];

LL fpow(LL bs, LL idx){
    LL res = 1;
    bs %= MOD;
    while(idx){
        if(idx & 1) (res *= bs) %= MOD;
        idx >>= 1;
        (bs *= bs) %= MOD;
    }
    return res;
}
inline LL inv(LL x){ return fpow(x, MOD - 2); }
inline LL C(LL x, LL y){ return fac[x] * inv(fac[y]) % MOD * inv(fac[x-y]) % MOD; }
inline LL getVal(LL r, LL c){
    LL res = 0;
    for(int i = 1; i <= c + 1; i++)
        (res += C(r + i, i)) %= MOD;
    return res % MOD;
}

int main(){
    fac[0] = 1;
    for(int i = 1; i <= 2e6+100; i++)
        fac[i] = (fac[i-1] * (LL)i) % MOD;
    read(r1, c1, r2, c2);
    LL ans = getVal(r2, c2) - getVal(r1-1, c2) - getVal(r2, c1-1) + getVal(r1-1, c1-1);
    ((ans %= MOD) += MOD) %= MOD;
    printf("%lld\n", ans);
    return 0;
}