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+7;
typedef long long ll;
ll fac[8010],inv[8010],ans=0;
int n;
int a[200010],b[200010],f[4010][4010];
ll C(int x,int y){return fac[x]*inv[y]%mod*inv[x-y]%mod;}
int main()
{
fac[0]=fac[1]=inv[0]=inv[1]=1;
for (int i=2;i<=8000;i++) fac[i]=i*fac[i-1]%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for (int i=2;i<=8000;i++) inv[i]=inv[i]*inv[i-1]%mod;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
f[2000-a[i]][2000-b[i]]++;
}
for (int i=0;i<=4000;i++) for (int j=0;j<=4000;j++)
{
if (i) f[i][j]+=f[i-1][j];if (f[i][j]>=mod) f[i][j]-=mod;
if (j) f[i][j]+=f[i][j-1];if (f[i][j]>=mod) f[i][j]-=mod;
}
for (int i=1;i<=n;i++)
{
ans+=f[2000+a[i]][2000+b[i]];if (ans>=mod) ans-=mod;
ans-=C((a[i]+b[i])<<1,a[i]<<1);
if (ans<0) ans+=mod;
}
ans=ans*inv[2]%mod;
cout<<ans;
}
转载于:https://www.cnblogs.com/coco-night/p/9677583.html