【題目敘述】https://atcoder.jp/contests/abc154/tasks/abc154_f
【解題想法】模逆元 (modular multiplicative inverse)【參考】
- 題目要計算 the sum of f(i, j) over all pair of integers (i, j) such that r1≤i≤r2 and c1≤j≤c2。
- 令 g(r, c) 為所有滿足0≤i≤r和0≤j≤c的整數對(i, j) 的 f(i, j)的總和，則答案為g(r2, c2) – g(r1-1, c2) – g(r2, c1-1) + g(r1-1, c1-1)。
- 需要能快速計算 g(r, c) 的方法。
- 考慮從點 (0, 0) 到點 (r + 1, c) 的任何路徑都是 從點 (0, 0) 到點 (r, 0)，然後繼續到 (r + 1, 0)，再移至點 (r + 1, c)。因此，
- f(r + 1, c) = f(r, 0) + f(r, 1) + … + f(r, c)
- f(r, c) = (r+c 個取 c 個的組合數目) = (r + c)! / (r! c!)
- 需要預先計算 階乘 和 階乘的逆元。
- inv[n] = n 的逆元 (mod p)
- 公式：inv[n]= – (p/n) * inv[p%n]
- 為避免負數，inv[n]= p – (p/n) * inv[p%n]
- pre[n] = n! % mod
- prei[n] = (1 / n!) % mod
- 最後的答案，排容計算後可能是負值，因此先加上mod*2後，再取mod。
#include <iostream>
using namespace std;
#define ll long long
const int mod = 1e9+7, maxn = 2000010;
int r1, c1, r2, c2;
ll pre[maxn];
ll inv[maxn];
ll prei[maxn];
void build(int n){
pre[1] = pre[0] = 1, inv[1] = inv[0] = 1, prei[1] = prei[0] = 1;
for(int i = 2 ; i <= n ; i++){
pre[i] = pre[i-1] * i % mod;
inv[i] = (mod - mod / i * inv[mod % i] % mod) % mod;
//或 inv[i] = mod - (mod / i * inv[mod % i]) % mod;
prei[i] = prei[i-1] * inv[i] % mod;
}
}
ll C(int n, int k){
return pre[n] * prei[k] % mod * prei[n-k] % mod;
}
ll solve(int x, int y){
if (x == 0 || y == 0) return 0;
ll ret = 0;
for (int i = 1; i <= y; i++){
ret += C(x+i+1, i+1);
}
ret -= y;
return ret % mod;
}
int main(){
build(2000005);
cin >> r1 >> c1 >> r2 >> c2;
cout << (solve(r2, c2)-solve(r1-1, c2)-solve(r2, c1-1)+solve(r1-1, c1-1)+mod*2)%mod << "\n";
}