这是一篇能让像我一样蒻的蒟蒻看的懂题解

50分做法：

预处理阶乘及阶乘逆元，然后枚举每一个 $i,j$ ，O(1)计算出 $\binom{a_i+a_j+b_i+b_j}{a_i+a_j}$ ，将结果全部相加即可。

正解：

我们先考虑将50分的做法优化。

可是我们发现，50分的做法一定要枚举每一个 $i,j$ ，才能计算出组合数的值，复杂度一定是 $O(n^2)$ 的，无法优化，于是我们只能放弃这种做法，另辟蹊径。

我们来看题目的取值范围 $2≦N≦200,000,1≦A_i≦2000,1≦B_i≦2000$

我们发现，虽然 $N$ 很大，但是 $A_i,B_i$ 都很小，所以我们可以考虑在这上面下手。

观察题目所求的组合数的形式，我们可以联想到组合数的几何意义: $\binom{x+y}{x}$ 其实就是从点 $(0,0)$ 到点 $(x,y)$ ，每次只能向上或者向右的不同的走法的方案数。

有了这个性质之后，我们就可以进行一个dp。设 $f[i][j]$ 表示从点 $(0,0)$ 到点 $(i,j)$ 的路径条数，则显然有 $f[i][j]=f[i-1][j]+f[i][j-1]$ 。由于 $1≦A_i,B_i≦2000$ ，这个dp在时间复杂度上是吃得消的。

但是问题又来了：我们预处理好dp数组之后，对于每一个 $i,j$ 我们都需要统计一遍 $f[A_i+A_j][B_i+B_j]$ ，而这个统计依然是 $O(n^2)$ 的。同样，我们考虑优化。

我们希望可以 $O(n)$ 统计，即方案数只跟每一个 $i$ 相关。我们发现我们要到达的点与 $i,j$ 的取值都是有关的，所以我们希望能够 (控制单一变量) 控制它的取值只和其中的一个有关，所以我们想把 $i$ 这一维给消掉。如何消掉呢？我们考虑平移。

将从 $(0,0)$ 到 $(A_i+A_j,B_i+B_j)$ 平移成从 $(-A_i,-B_i)$ 到 $(A_j,B_j)$ ，相当于坐标的左边同时减去 $A_i$ ，右边同时减去 $B_i$ ，这样所得的新的方案数与原来的是相同的。

为什么呢？我们分别以起点和终点的坐标为左下角，右上角的顶点，画出一个矩形，只要这个矩形的长和宽不变，那么从左下角的顶点到右上角的顶点的方案数一定是不变的。而我们的平移，只改变了矩形的位置，并没有改变矩形的长和宽，因此是可行的。

平移完之后就简单了。我们的起点只与 $i$ 有关，终点只与 $j$ 有关。所以我们一次性将所有的 $f[-A_i][-B_i]$ 加一，这样我们的 $f[i][j]$ 就变成从点 $(i,j)$ 到所有的 $(-A_i,-B_i)$ 的路径条数之和。最后的结果自然就是把每一个 $f[A_i][B_i]$ 加起来了。但是要注意，题目中要求 $i!=j$ ，所以我们要减去从 $(-A_i,-B_i)$ 到 $(A_i,B_i)$ 的路径条数。这个我们可以用组合数算，路径条数为 $\binom{2A_i+2B_i}{2A_i}$ 。全部减完之后，又因为题目要求 $i<j$ ，所以我们还要将最后的结果除以二。

时间复杂度： $O((max(A_i)+max(B_i))^2+N)$

Code:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define rg register
using namespace std;
const int MAXN1=2e5+50,MAXN2=2100,MOD=1e9+7,S=2050;
typedef long long LL;
LL N,a[MAXN1],b[MAXN1],mul[MAXN2<<2],invv[MAXN2<<2],f[MAXN2<<1][MAXN2<<1],ans=0;
inline LL qpow(LL a,LL b){//快速幂 
	LL res=1;
	while(b){
		if(b&1) res=(res*a)%MOD;
		b>>=1;
		a=(a*a)%MOD;
	}
	return res;
}
inline LL inv(LL x){return qpow(x,MOD-2)%MOD;}//求逆元 
inline LL C(LL n,LL m){return mul[n]*invv[n-m]%MOD*invv[m]%MOD;}//求组合数 
int main()
{
	memset(f,0,sizeof(f));
	scanf("%lld",&N);
	for(rg LL i=1;i<=N;i++) scanf("%lld%lld",&a[i],&b[i]),f[S-a[i]][S-b[i]]++;//将所有的起点的dp值都加一 
	mul[0]=1,invv[0]=inv(mul[0]);//预处理阶乘及阶乘逆元 
	for(rg LL i=1;i<=8000;i++) mul[i]=mul[i-1]*i%MOD,invv[i]=inv(mul[i]);
	for(rg LL i=1;i<=S*2;i++)//dp 
		for(rg LL j=1;j<=S*2;j++)
			f[i][j]=(f[i][j]+(f[i-1][j]+f[i][j-1])%MOD)%MOD;
	for(rg LL i=1;i<=N;i++){
		ans=(ans+f[S+a[i]][S+b[i]])%MOD;//累加答案 
		ans=(ans-C(2*a[i]+2*b[i],2*a[i]))%MOD;//减去重复计算的 
		ans=(ans+MOD)%MOD;//防止ans为负数 
	}
	ans=(ans*500000004)%MOD;//除以二，也就是乘2的逆元 
	printf("%lld\n",ans);
	return 0;
}