火题小战 B. barbeque

题目描述

(Robbery) 是一个大吃货（雾）

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

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

（请参考图片以理解样例）

输入格式

第一行为整数(n)

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

输出格式

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

样例

样例输入

3
1 1
1 1
2 1

样例输出

26

数据范围与提示

对于(30\%)的数据，保证(n leq 5000)
对于另外(30\%)的数据，保证(nleq 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
",(long long)ans*ny[2]%mod);
	return 0;
}