火题小战 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;

}