题目链接：传送门

Description

求∑i=1n∑j=1i−1(Ai+Bi+Aj+BjAi+Aj)\sum_{i=1}^{n}\sum_{j=1}^{i-1}\binom{A_i+B_i+A_j+B_j}{A_i+A_j}

Solution

我们通过观察式子可以发现题目就是要求所有(−Ai,−Bi)(-A_i,-B_i)到(Aj,Bj)(A_j,B_j)的方案数（只能向上走或者向右走），于是我们可以用Dp来解决，初始化时在每个Dp[−A[i]][−B[i]]Dp[-A[i]] [-B[i]]处++，然后直接用Dp[i][j]+=Dp[i−1][j]+Dp[i][j−1]Dp[i][j]+=Dp[i-1][j]+Dp[i][j-1]统计答案即可 然后因为我们求的j是< i的，所以需要减去一个(−A[i],−B[i])(-A[i],-B[i])到自己的方案，并且最后的ans要除以2

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int Maxn = 200000, Maxm = 4000, Mod = (int)(1e9 + 7);

int A[Maxn + 10], B[Maxn + 10], Dp[Maxm * 2 + 10][Maxm * 2 + 10], fac[Maxn + 10], inv[Maxn + 10];
int N;

inline int Pow (LL a, int b)
{
    LL ans = 1;
    while (b)
    {
        if (b & 1) (ans *= a) %= Mod;
        (a *= a) %= Mod;
        b >>= 1;
    }
    return ans;
}

inline int C (int n, int m)
{
    return ((LL)fac[n] * inv[m] % Mod * inv[n - m] % Mod);
}

main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%d", &N);
    fac[0] = 1;
    inv[0] = 1;
    for (int i = 1; i <= Maxn + 1; ++i) fac[i] = ((LL)fac[i - 1] * i) % Mod, inv[i] = Pow(fac[i], Mod - 2);
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d%d", &A[i], &B[i]);
        Dp[2001 - A[i]][2001 - B[i]] ++;
        //cout<<Maxm + 1 - A[i]<<" "<<Maxm + 1 - B[i]<<endl;
    }
    for (int i = 1; i <= Maxm + 2; ++i)
        for (int j = 1; j <= Maxm + 2; ++j)
            (Dp[i][j] += Dp[i][j - 1] + Dp[i - 1][j]) %= Mod;
    LL ans = 0;
    for (int i = 1; i <= N; ++i)
    {
        ans += Dp[A[i] + 2001][B[i] + 2001];
        ans = ((ans - C(A[i] + A[i] + B[i] + B[i], A[i] + A[i])) % Mod + Mod) % Mod;
    }
    printf("%d\n", ans * inv[2] % Mod);
    return 0;
}