题意

求\(\sum_{i=1}^{n} \sum_{j=i+1}^{n} \dbinom{a_i+a_j}{a_i+b_i+a_j+b_j}\)

解法

考虑\(\dbinom{a_i+a_j}{a_i+b_i+a_j+b_j}\)的几何意义,由\(\dbinom{x}{x+y}\)的意义可知这等价于从\((0, \; 0)\)走到\((a_i+a_j,\; b_i+b_j)\)的路径条数,即从\((-a_i, \; -b_i)\)走到\((a_j, \; b_j)\)的路径条数

对于路径条数,我们有dp: \(dp(i,\; j)=dp(i-1, \; j)+dp(i,\; j-1)\),在本题中由于值域较小可以使用,只需在起始时给每个\((-a_i, \; -b_i)\)都加上1(作为起点)即可

正确性显然

代码

#include
    
     using namespace std;#define int long longconst int Mod = 1e9+7 ;const int mxn = 2e6 ;const int N=200005, M=8000;int frac[mxn+5], inv[mxn+5];int dp[M/2+5][M/2+5], base=M/4+2;int n, a[N], b[N];int power(int a, int b){    int res=1, car=a;     while(b){        if(b&1) (res*=car)%=Mod;        (car*=car)%=Mod;        b>>=1;    }    return res;}void init(){    frac[0]=1 ;    for(int i=1;i
     
      0;--i) inv[i]=(inv[i+1]*(i+1))%Mod ;    inv[0] = 1 ;}int C(int n, int k){    return ((frac[n]*inv[k]%Mod)*inv[n-k])%Mod ;}long long ans = Mod ;signed main(){    init() ; cin>>n;    for(int i=1;i<=n;++i) cin>>a[i]>>b[i], ++dp[base-a[i]][base-b[i]];    for(int i=1;i<=M/2+2;++i) for(int j=1;j<=M/2+2;++j) (dp[i][j]+=(dp[i-1][j]+dp[i][j-1]))%=Mod;    for(int i=1;i<=n;++i) (ans+=dp[a[i]+base][b[i]+base]), (ans-=C(2*a[i]+2*b[i], 2*a[i]))%=Mod ; (ans+=Mod)%=Mod ;    cout<<(ans*power(2, Mod-2))%Mod<