[AGC001E] BBQ Hard

题面

有 $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$ 取模。

$n\leq10^5,a_i,b_i\leq2000$ 。

题解

考虑组合意义，相当于横着走 $a_i+a_j$ 竖着走 $b_i+b_j$ 。

这个 $i,j$ 在一起很烦人，考虑转为从 $(-a_i,-b_i)$ 走到 $(a_j,b_j)$ 。然后平方做即可。

代码

const int N = 4510, M = 2e5 + 5, O = 2001, mod = 1e9 + 7;

ll Read(){
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	ll n, a[M], b[M], ans;
	ll f[N][N], fac[M], inv[M];
	ll qpow (ll a, ll b){
		ll ans = 1;
		for (; b; b >>= 1, a = a * a % mod)
			if (b & 1) ans = ans * a % mod;
		return ans;
	}
	ll C(int n, int m){
		if (n < m) return 0;
		return fac[n] * inv[n - m] %  mod * inv[m] % mod;
	}
	int main() {
		fac[0] = 1;
		for (int i = 1; i <= M - 10; i++) fac[i] = fac[i - 1] * i % mod;
		inv[M - 10] = qpow (fac[M - 10], mod - 2);
		for (int i = M - 10; i; i--) inv[i - 1] = inv[i] * i % mod;
		n = Read();
		for (int i = 1; i <= n; i++){
			a[i] = Read(), b[i] = Read();
			f[O - a[i]][O - b[i]]++;
		}
		for (int i = 1; i <= O * 2; i++)
			for (int j = 1; j <= O * 2; j++)
				(f[i][j] += f[i-1][j] + f[i][j-1]) %= mod;
		for (int i = 1; i <= n; i++) {
			ans = (ans + f[O + a[i]][O + b[i]]) % mod;
			ans = (ans - C(2 * a[i] + 2 * b[i], 2 * b[i]) + mod) % mod;
			for (; ans < 0; ans += mod);
		}
		ans = ans * inv[2] % mod;
		printf ("%lld\n", ans);
		return 0;
	}
}

int main (){
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	Main::main();
	return 0;
}