AtCoder

Luogu

分析

观察题目中给的这个式子
$$
a_i+a_j+b_i+b_j\choose a_i+a_j
$$
等价于从 $(0,0)$ 走到 $(a_i+a_j,b_i+b_j)$ 的方案数，等价于从 $(-a_i,-b_i)$ 走到 $(a_j,b_j)$ 的方案数。

然后题目中要求的是 $\sum$，因此我们考虑求出以每个 $(-a_i,-b_i)$ 为起点走到每个 $(a_j,b_j)$ 的方案数之和。

注意到 $a_i,b_i$ 的范围很小，因此我们直接在网格图上递推即可。

但是这样子多算了从 $(-a_i,-b_i)$ 走到 $(a_i,b_i)$ 的方案数，我们可以直接把这一部分减掉；还多算了 $i>j$ 的部分，我们可以直接把答案除以 $2$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int mod=1e9+7;
inline int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

const int N=200000+10,SIZE=2001,L=(SIZE<<2)+10;

int fac[L],ifac[L];
inline void init(int n) {
    fac[0]=1;
    for (re int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for (re int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
}
inline int C(int n,int m) {
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

int n,a[N],b[N],dp[L][L];

int main() { init(SIZE<<2);
    n=read();
    for (re int i=1;i<=n;++i) {
        a[i]=read(),b[i]=read();
        ++dp[SIZE-a[i]][SIZE-b[i]];
    }
    for (re int i=1;i<=SIZE<<1;++i)
        for (re int j=1;j<=SIZE<<1;++j)
            dp[i][j]=(dp[i][j]+dp[i-1][j]+dp[i][j-1])%mod;
    int ans=0;
    for (re int i=1;i<=n;++i) {
        ans=(ans+dp[SIZE+a[i]][SIZE+b[i]])%mod;
        ans=(ans-C(a[i]+a[i]+b[i]+b[i],a[i]+a[i])+mod)%mod;
    }
    printf("%lld\n",1ll*ans*qpow(2,mod-2)%mod);
    return 0;
}