AT1983 in luogu

题意

求如下式子，答案对 109+710^9+7 取模

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

$ 1\le n\le 200,000,;1\le A_i,B_i\le 2,000$

题解

考虑组合意义，对于 (Ai+Bi+Aj+BjAi+Aj)\binom{A_i+B_i+A_j+B_j}{A_i+A_j} ，其含义为 (−Ai,−Bi)→(Aj,Bj)(-A_i,-B_i) \to (A_j,B_j) 每次向上 11 或向右 11 的路径方案数，因为值域很小，这种路径方案数还可以用 DP 做： fi,j=fi−1,j+fi,j−1f_{i,j}=f_{i-1,j}+f_{i,j-1} 多个起点也是可以一起做的，答案就是：

12⋅∑i=1n(fAi,Bi−(2Ai+2Bi2Ai))\frac{1}{2}\cdot \sum_{i=1}^n \left(f_{A_i,B_i}-\binom{2A_i+2B_i}{2A_i}\right)

复杂度 O(n+Amax⁡Bmax⁡)O(n+A_{\max}B_{\max})

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
#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void red(T &x) {
    x=0;bool fg=0;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(T)(ch^48),ch=getchar();
    if(fg) x=-x;
}
const int N = 200010;
const int M = 2005;
const int mod = 1e9+7;
const int e = 2001;
int n,A[N],B[N],f[M<<1][M<<1];
int fac[M<<2]={1,1},ifac[M<<2]={1,1},inv[M<<2]={1,1};
int C(int n,int m) {
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void Add(int &x,int y) {x=(1ll*x+y+mod)%mod;}
int main() {
    red(n);
    for(int i=2;i<=8010;i++) 
        fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod,ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
    for(int i=1;i<=n;i++) red(A[i]),red(B[i]);
    for(int i=1;i<=n;i++) f[e-A[i]][e-B[i]]++;
    for(int i=1;i<=2*e;i++) {
        for(int j=1;j<=2*e;j++) {
            Add(f[i][j],f[i-1][j]);
            Add(f[i][j],f[i][j-1]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++) Add(ans,f[e+A[i]][e+B[i]]);
    for(int i=1;i<=n;i++) Add(ans,-C(2*A[i]+2*B[i],2*A[i]));
    ans=(1ll*ans*inv[2])%mod;
    printf("%d\n",ans);
    return 0;
}