Barbeque ： ATcoder1983改编
题目描述
(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 leqslant 5000)
对于另外(30\%)的数据，保证(nleqslant 1e5,a_i,b_i leqslant 100)
对于所有数据，保证(2 leqslant n leqslant 2e5,1 leqslant a_i,b_i leqslant 2000)
分析
如果数据范围小的话，这个题就是就是一眼题，直接求一个组合数 (C_{a[i]+a[j]+b[i]+b[j]}^{a[i]+a[j]}) 就行。但是对一这道题的数据范围，肯定会 (T) ，所以我们换一个方向来求解组合数。
考虑一下组合数的几何定义，这个组合数的式子不就是从 ((0,0)) 到 ((a[i]+a[j],b[i]+b[j])) 的不同路径的方案数吗，那么我们就可以根据这一性质来进行 (dp) 求出方案数。
因为从 ((0,0)) 到 ((a[i]+a[j],b[i]+b[j])) 中，坐标既有 (i) ，又有 (j) ，所以我们把横坐标减去 (a[j]) ，纵坐标减去 (b[j]) ，那横纵坐标就只剩下一种了，我们就可以直接 (dp) 。
负数下标的处理就是直接加上一个极大值。因为 (i) 和 (j) 都是从 (1) 开始枚举的，所以会有起点终点反过来的情况，那么最后的答案要除以 (2) ，也就是乘以 (2) 的逆元。还有开始和结束是同一点的情况，减去一个 (C_{2*a[i]+2*b[i]}^{2*a[i]}) 即可。
代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn = 2e3+100;
const int maxm = 2e5+10;
const int mod = 1e9+7;
const int base = 2e3+40;
int a[maxm],b[maxm];
int f[maxn*2][2*maxn];
int jc[maxm],ny[maxm],jcny[maxm];
int getC(int n,int m){
return (ll)jc[n] % mod * (ll)jcny[m] % mod * (ll)jcny[n-m] % mod;
}
signed main(){
ll ans = 0;
ny[1] = 1;
for(int i=2;i<maxm;++i){
ny[i] = (ll)(mod - mod / i) % mod * (ll)ny[mod % i] % mod;
}
jc[0] = jcny[0] = 1;
for(int i=1;i<maxm;++i){
jc[i] = (ll)jc[i-1] * (ll)i % mod;
jcny[i] = (ll)jcny[i-1] * (ll)ny[i] % mod;
}
int n;
int Max = 0;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d",&a[i],&b[i]);
f[base-a[i]][base-b[i]] ++;
}
for(int i=1;i<=base*2;++i){
for(int j=1;j<=base*2;++j){
f[i][j] = (ll)((ll)f[i][j] + (ll)((ll)f[i][j-1] + (ll)f[i-1][j])%mod) % mod;
}
}
for(int i=1;i<=n;++i){
ans = (ans + (ll)f[base + a[i]][base + b[i]]) % mod;
ans = (ans - (ll)getC(2 * a[i] + 2 * b[i],2 * a[i])) % mod;
ans = (ans + mod) % mod;
}
ans = (ans * (ll)ny[2] % mod) % mod;
printf("%lld
",ans);
return 0;
}