2019/03/10 20:23

洛谷题目链接:BBQ Hard

题意翻译

• $2≦N≦200,000$
• $1≦A_i≦2000,\ 1≦B_i≦2000$

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
const int BASE = 2002;
const int mod = 1e9+7;

int n, a[N], b[N], ans = 0, f[BASE*2+5][BASE*2+5], inv[N], fac[N], pinv[N];

void init(){
fac[0] = inv[0] = pinv[0] = fac[1] = inv[1] = pinv[1] = 1;
for(int i = 2; i <= BASE*4; i++){
fac[i] = 1ll*fac[i-1]*i%mod;
inv[i] = 1ll*(mod-mod/i)*inv[mod%i]%mod;
pinv[i] = 1ll*pinv[i-1]*inv[i]%mod;
}
}

int C(int n, int m){ return 1ll*fac[n]*pinv[m]%mod*pinv[n-m]%mod; }

int main(){
ios::sync_with_stdio(false);
cin >> n, init();
for(int i = 1; i <= n; i++)
cin >> a[i] >> b[i], f[BASE-a[i]][BASE-b[i]]++;
for(int i = 1; i <= BASE*2; i++)
for(int j = 1; j <= BASE*2; j++)
(f[i][j] += (f[i-1][j]+f[i][j-1])%mod) %= mod;
for(int i = 1; i <= n; i++) (ans += f[a[i]+BASE][b[i]+BASE]) %= mod;
for(int i = 1; i <= n; i++) (ans += mod-C((a[i]+b[i])*2, b[i]*2)) %= mod;
ans = 1ll*ans*inv[2]%mod;
cout << ans << endl;
return 0;
}


0
0 收藏

0 评论
0 收藏
0