Description
Solution
题目简化后要求的实际上是$\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}C^{A[i]+A[j]}_{A[i]+A[j]+B[i]+B[j]}$
这时看看n的数据范围瞬间绝望qaq。
不过看到A,B的数据范围似乎明白了什么。。。好像是O(n2)的是不是?
关键:从(0,0)走到(m,n)且只能往上和右走的方案数为$C_{n+m}^{n}$
所以$C^{A[i]+A[j]}_{A[i]+A[j]+B[i]+B[j]}$等价于从(-A[i],-B[i])到(A[j],B[j])并且只能往上和右走的方案数。
em突然开心。我们把所有dp[2000-A[i]][2000-B[i]]++。
转移$dp[i][j]=dp[i-1][j]+dp[i][j-1]$显然。
接着我们到dp[2000+A[i]][2000+B[i]]处统计答案。不过要减去从(2000-A[i],2000-B[i]])到(2000+A[i],2000+B[i]])的方案数(直接组合数)
最后答案除以2。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int mod=1e9+;
typedef long long ll;
ll fac[],inv[],ans=;
int n;
int a[],b[],f[][];
ll C(int x,int y){return fac[x]*inv[y]%mod*inv[x-y]%mod;}
int main()
{
fac[]=fac[]=inv[]=inv[]=;
for (int i=;i<=;i++) fac[i]=i*fac[i-]%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for (int i=;i<=;i++) inv[i]=inv[i]*inv[i-]%mod;
scanf("%d",&n);
for (int i=;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
f[-a[i]][-b[i]]++;
}
for (int i=;i<=;i++) for (int j=;j<=;j++)
{
if (i) f[i][j]+=f[i-][j];if (f[i][j]>=mod) f[i][j]-=mod;
if (j) f[i][j]+=f[i][j-];if (f[i][j]>=mod) f[i][j]-=mod;
}
for (int i=;i<=n;i++)
{
ans+=f[+a[i]][+b[i]];if (ans>=mod) ans-=mod;
ans-=C((a[i]+b[i])<<,a[i]<<);
if (ans<) ans+=mod;
}
ans=ans*inv[]%mod;
cout<<ans;
}