Blog

题目

Atcoder

思路

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 4030, M = 200010, D = 2010, mod = 1e9 + 7;
int n, m, f[N][N], fact[N << 1], invf[N << 1];
int A[M], B[M];
int qmi(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1) res = a * res % mod;
    return res % mod;
}
int inv(int x) { return qmi(x, mod - 2); }
int C(int a, int b) { return fact[a] * invf[b] % mod * invf[a - b] % mod; }
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++)   // 防止数组越界加个偏移量 D 
        cin >> A[i] >> B[i], f[D - A[i]][D - B[i]]++;
    for (int i = 1; i < N; i++)
        for (int j = 1; j < N; j++)
            f[i][j] = (f[i][j] + (f[i - 1][j] + f[i][j - 1]) % mod) % mod;
    fact[0] = 1, invf[0] = inv(1);
    for (int i = 1; i <= 8000; i++) 
        fact[i] = fact[i - 1] * i % mod, invf[i] = inv(fact[i]);
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = (res + f[D + A[i]][D + B[i]]) % mod;
        res = ((res - C(2 * A[i] + 2 * B[i], 2 * A[i])) % mod + mod) % mod;
    }
    cout << res * inv(2) % mod << endl;
    return 0;
}