Submission #1383687

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxx = 4004, maxn = 2e5 + 20, mod = 1e9 + 7, gaam = 2001;

ll dp[maxx][maxx], fac[maxn], a[maxn], b[maxn], n;

ll pw(ll a, ll b)
{
	if (!b) return 1ll;
	ll x = pw(a, b / 2);
	x = (x * x) % mod;
	if (b % 2) x = (x * a) % mod;
	return x;
}

ll sel(ll a, ll b)
{
	ll x = 1ll;
	x = (x * fac[a]) % mod;
	x = (x * pw(fac[b], mod - 2)) % mod;
	x = (x * pw(fac[a-b], mod - 2)) % mod;
	return x;
}




int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	fac[0] = 1ll;
	for(ll i = 1; i < maxn; i++) fac[i] = (fac[i - 1] * 1ll * i) % mod;
	cin >> n;
	for(ll i = 0; i < n; i++) cin >> a[i] >> b[i], dp[-a[i] + gaam][-b[i] + gaam] += 1;
	for(ll i = -gaam; i <= gaam; i++)
		for(ll j = -gaam; j <= gaam; j++)
	//		if (dp[i + gaam][j + gaam] == 0)
				dp[i + gaam][j + gaam] = (dp[i + gaam][j + gaam] + ((i + gaam) ? dp[i-1 + gaam][j + gaam] : 0ll) 
															 + ((j + gaam) ? dp[i + gaam][j-1 + gaam] : 0ll)) % mod;
//			cout << i << " " << j << "   " << dp[i + gaam][j + gaam] << endl;
	ll ans = 0;
	for(ll i = 0; i < n; i++) ans = (ans + dp[a[i] + gaam][b[i] + gaam]) % mod, 
							   ans = (((ans - sel(a[i]*2 + b[i]*2, a[i]*2)) % mod) + mod) % mod;
	ans = (ans * pw(2, mod - 2)) % mod;
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result