火题小战 B. barbeque

题目描述

\(Robbery\) 是一个大吃货(雾)

某个神奇的串由牛肉和青椒构成,于是\(Robbery\)购买了\(n\)个餐包来自己做这个串,每个餐包中有一些牛肉,青椒和一些特殊的调料(我们认为所有的牛肉和青椒都是一样的,但是调料各不相同)

当拿出所有的餐包后,\(Robbery\)突然想到一个问题,假如将所有餐包两两组合,将选中的两个餐包中的所有牛肉和青椒串在一起,能够组合出多少串的方法

(请参考图片以理解样例)

输入格式

第一行为整数\(n\)

接下来\(n\)行每行两个整数\(a_i\)和\(b\) 表示第\(i\)个餐包中有\(a_i\)块牛肉,\(b_i\)块青椒

输出格式

输出一个整数表示串的总方案数,最终结果对\(1e9+7\)取模

样例

样例输入

样例输出

数据范围与提示

对于\(30\%\)的数据,保证\(n \leq 5000\)

对于另外\(30\%\)的数据,保证\(n\leq 1e5,a_i,b_i \leq 100\)

对于所有数据,保证\(2 \leq n \leq 2e5,1 \leq a_i,b_i \leq 2000\)

分析

这一道题的暴力是比较好打的,我们两两枚举 \(i,j\) ,每次计算 \(C_{a[i]+a[j]+b[i]+b[j]}^{a[i]+a[j]}\) 将价值累加即可

我们会发现,暴力的算法总会枚举 \(i\) 和 \(j\),这样的效率肯定是 \(n^2\) 的

于是,我们考虑组合数的几何意义

我们可以把 \(C_{n+m}^{n}\) 看成从原点出发,只能向上或者向右走,到达坐标为 \((n,m)\) 的点的方案数

因此上面的式子可以理解到达坐标为 \((a[i]+a[j],b[i]+b[j])\) 的点的方案数

我们将原点和目标点向左下方平移,即同时减去 \((a[i],b[i])\)

这样出发点就变成了 \((-a[i],-b[i])\) ,终点就变成了 \((a[j],b[j])\)

这样就不用分别枚举 \(i\) 和 \(j\)

此时我们设 \(f[i][j]\) 为 \(n\) 个点走到 \((i,j)\) 的方案数之和

初始时我们要把 \(f[-a[i]][-b[i]]\) 加一

转移时,根据组合数的性质,有 \(f[i][j]+=f[i-1][j]+f[i][j-1]\)

最后统计答案时,我们要把自己到自己的贡献减去,还要把起点终点互换的情况减去

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+101;
const int mod=1e9+7;
int n,m,a[maxn*100],b[maxn*100],ny[maxn*4],jc[maxn*4],jcc[maxn*4],f[maxn*2][maxn*2],s=2050;
long long getC(int n,int m){
return (long long)jc[n]%mod*jcc[n-m]%mod*jcc[m]%mod;
}
int main(){
scanf("%d",&n);
ny[1]=1;
for(int i=2;i<maxn*4;i++){
ny[i]=(long long)((long long)mod-mod/i)*ny[mod%i]%mod;
}
jc[0]=jcc[0]=1;
for(int i=1;i<maxn*4;i++){
jc[i]=(long long)jc[i-1]*i%mod;
jcc[i]=(long long)jcc[i-1]*ny[i]%mod;
}
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
f[s-a[i]][s-b[i]]++;
}
for(int i=1;i<2*maxn-5;i++){
for(int j=1;j<2*maxn-5;j++){
f[i][j]=(long long)((long long)f[i][j]%mod+(long long)f[i-1][j]%mod+(long long)f[i][j-1]%mod)%mod;
}
}
long long ans=0;
for(int i=1;i<=n;i++){
ans=(ans+(long long)f[s+a[i]][s+b[i]])%mod;
ans=(ans-getC(2*a[i]+2*b[i],2*a[i]))%mod;
ans=(ans+mod)%mod;
}
printf("%lld\n",(long long)ans*ny[2]%mod);
return 0;
}
05-21 02:25