Description
有(N(Nleq 200000))个数对((a_i,b_i)(a_i,b_i,leq 2000)),求出(sumlimits_{i=1}^nsumlimits_{j=i+1}^nC_{a_i+b_i+a_j+b_j}^{a_i+a_j}) 答案对(10^9+7)取模
Solution
首先考虑(C(n,m))的组合意义:在笛卡尔坐标系下只能向上和向右走,从原点走到((m,n-m))的路径总数。
所以这个(C_{a_i+b_i+a_j+b_j}^{a_i+a_j})就可以看成从((0,0))走到((a_i+a_j,b_i+b_j))的方案数,这个式子里有(i)的项和有(j)的项掺在了一起,尝试将他们拆开。这个方案数等价于从((-a_i,-b_i))走到((a_j,b_j))的方案数,这样一来(i)和(j)至少分开了。
然后试着不考虑(j>i)的限制,求出第三象限上所有点到((a_i,b_i))的方案数,再减去从((-a_i,-b_i))到((a_i,b_i))的方案数,再除以(2)就是就是最终的答案了。
可以设(f[i][j])表示第三象限内的点只能向上和向右走,走到((i,j))的方案数。初值是(f[a_i][b_i]=1),转移就是每个点可以从它的左边或者右边走过来(f[i][j]+=f[i-1][j]+f[i][j-1])。
Code
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<cctype>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using std::min;
using std::max;
using std::swap;
using std::vector;
const int M=2005;
const int N=200005;
const int ZYZ=1e9+7;
typedef double db;
typedef long long ll;
#define pb(A) push_back(A)
#define pii std::pair<int,int>
#define all(A) A.begin(),A.end()
#define mp(A,B) std::make_pair(A,B)
int n,a[N],b[N];
int f[M<<1][M<<1];
int fac[M<<2],ifac[M<<2];
int getint(){
int X=0,w=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while( isdigit(ch))X=X*10+ch-48,ch=getchar();
if(w) return -X;return X;
}
int ksm(int a,int b,int ans=1){
while(b){
if(b&1) ans=1ll*ans*a%ZYZ;
a=1ll*a*a%ZYZ;b>>=1;
}return ans;
}
void init(int n){
fac[0]=ifac[0]=1;
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%ZYZ;
ifac[n]=ksm(fac[n],ZYZ-2);
for(int i=n-1;i;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%ZYZ;
}
int C(int n,int m){
return 1ll*fac[n]*ifac[m]%ZYZ*ifac[n-m]%ZYZ;
}
signed main(){
init(8000);
n=getint();
for(int i=1;i<=n;i++){
a[i]=getint(),b[i]=getint();
f[2001-a[i]][2001-b[i]]++;
}
for(int i=1;i<=4001;i++)
for(int j=1;j<=4001;j++)
f[i][j]=(1ll*f[i][j]+f[i-1][j]+f[i][j-1])%ZYZ;
int ans=0;
for(int i=1;i<=n;i++) ans=(ans+f[a[i]+2001][b[i]+2001])%ZYZ;
for(int i=1;i<=n;i++) ans=(ans-C(a[i]+b[i]<<1,b[i]<<1)+ZYZ)%ZYZ;
printf("%lld
",1ll*ans*ksm(2,ZYZ-2)%ZYZ);
return 0;
}