Many Many Paths（组合计数）

题意

给定\(r1, c1, r2, c2\)，求\(\sum\limits_{i=r1}^{r2} \sum\limits_{j=c1}^{c2} f(i,j)\)，其中\(f(i,j)\)表示从\((0,0)\)往上或者往右走到\((i,j)\)的方案数。

题目链接：https://atcoder.jp/contests/abc154/tasks/abc154_f

数据范围

\(1 \leq r_1 \leq r_2 \leq 10^6\)
\(1 \leq c_1 \leq c_2 \leq 10^6\)

思路

参考blog：https://www.cnblogs.com/lllxq/p/12354597.html

第五行的公式，在前面加上一个\(\binom{i+1}{0}\)，再减去一个\(\binom{i+1}{0}\)，即可得到。

代码

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

using namespace std;

typedef long long ll;

const int N = 2000010, mod = 1e9 + 7;

int r1, c1, r2, c2;
ll fac[N], infac[N];

ll qmi(ll a, ll b)
{
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

ll inv(ll a)
{
    return qmi(a, mod - 2);
}

ll C(ll x, ll y)
{
    return fac[x] * infac[y] % mod * infac[x - y] % mod;
}

void init()
{
    fac[0] = infac[0] = 1;
    for(int i = 1; i < N; i ++) fac[i] = fac[i - 1] * i % mod;
    for(int i = 1; i < N; i ++) infac[i] = infac[i - 1] * inv(i) % mod;
}

ll calc(int a, int b)
{
    ll res = 0;
    for(int i = 0; i <= a; i ++) {
        res = (res + C(i + b + 1, b)) % mod;
    }
    return res;
}

int main()
{
    init();
    scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
    printf("%lld\n", ((calc(r2, c2) - calc(r1 - 1, c2) - calc(r2, c1 - 1) + calc(r1 - 1, c1 - 1)) % mod + mod) % mod);
    return 0;
}