【AGC001E】BBQ Hard

题目

题目链接：https://atcoder.jp/contests/agc001/tasks/agc001_e
有 n 个数对 ((a_i,b_i))，求

[sum_{i=1}^{n}sum_{j=i + 1}^{n}{a_i+b_i+a_j+b_j choose a_i+a_j} ]

答案对 (10^9+7) 取模。
(nleq 200000;1leq a_i,b_ileq 2000)。

思路

观察到 (a,b) 的取值范围很小，所以复杂度肯定是有关 (a,b) 的。
考虑 ({a_i+b_i+a_j+b_j choose a_i+a_j}) 的组合意义，其实就是从 ((0,0)) 走到 ((a_i+a_j,b_i+b_j)) 且只能往上和往右的方案数。
这样还是不好搞，我们可以把起点和终点的横纵坐标分别减去 (a_i) 和 (b_i)，也就是从 ((-a_i,-b_i)) 走到 ((a_j,b_j)) 的方案数。
这样起点和终点就分别只和 (i,j) 有关了。初始化 (f[x][y]=) 集合 ({i|a_i=x,b_i=y}) 的大小，然后往右上方递推即可。
因为题目中要求 (i<j)，所以最后减去 (i=j) 的方案数后除以二即可。
时间复杂度 (O(n+AB))。其中 (A=max(a_i),B=max(b_i))。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=200010,M=2010,MOD=1e9+7;
int n,ans,a[N],b[N],f[2*M][2*M],g[2*M][2*M];

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		f[M-a[i]][M-b[i]]++;
	}
	g[1][1]=1;
	for (int i=1;i<=4015;i++)
		for (int j=1;j<=4015;j++)
		{
			f[i][j]=(f[i][j]+f[i-1][j]+f[i][j-1])%MOD;
			g[i][j]=(g[i][j]+g[i-1][j]+g[i][j-1])%MOD;
		}
	for (int i=1;i<=n;i++)
	{
		ans=(ans+f[a[i]+M][b[i]+M])%MOD;
		ans=(ans+MOD-g[a[i]*2+1][b[i]*2+1])%MOD;
	}
	cout<<500000004LL*ans%MOD;
	return 0;
}