题目链接
题目解法
很有技巧的一道题
观察数据范围发现 \(a_i,b_i\) 很小，所以考虑和值域有关的做法
从组合意义上考虑组合数，不难想到 \(\binom{a_i+b_i+a_j+b_j}{a_i+a_j}\) 为 \((0,0)\) 到 \((a_i+a_j,b_i+b_j)\) 的路径数
把 \(i,j\) 项分开可得为 \((-a_i,-b_i)\) 到 \((a_j,b_j)\) 的路径数
这不难直接 \(dp\)
时间复杂度 \(O((\max\{a_i\}+\max\{b_i\})^2)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int P=1e9+7,iv2=500000004,Det=2100,N=200100;
int n,a[N],b[N],C[(Det<<2)+10][(Det<<2)+10],f[(Det<<1)+10][(Det<<1)+10];
int main(){
n=read();
F(i,0,Det<<2) F(j,0,i) C[i][j]=(!j||i==j)?1:(C[i-1][j-1]+C[i-1][j])%P;
F(i,1,n) a[i]=read(),b[i]=read();
F(i,1,n) f[-a[i]+Det][-b[i]+Det]++;
F(i,1,Det<<1) F(j,1,Det<<1) f[i][j]=(1ll*f[i][j]+f[i-1][j]+f[i][j-1])%P;
int ans=0;
F(i,1,n) ans=(ans+f[a[i]+Det][b[i]+Det])%P;
F(i,1,n) ans=(ans-C[(a[i]+b[i])*2][a[i]*2]+P)%P;
printf("%d\n",1ll*ans*iv2%P);
return 0;
}