题目链接

AGC001 E - BBQ Hard

题解

考虑\(C(n+m,n)\)的组合意义

从\((0,0)\)走到\((n,m)\)的方案数

从\((x,y)\)走到\((x+n,y+m)\)的方案数

考虑\(C(a_i+b_i+a_j+b_j,a_i+b_i)\)的组合意义

从\((0,0)\)走到\((a_i+a_j,b_i+b_j)\)的方案数

从\((-a_i,-b_i)\)走到\((a_j,b_j)\)的方案数

考虑计算任意\((-a_i,-b_i)\)到任意\((a_i,b_i)\)的方案数

减去从自己到自己的就好了

代码

#include<cstdio>

#include<algorithm>

#include<cstring>

#define gc getchar()

#define pc putchar

inline int read() {

	int x = 0,f = 1;

	char c = gc;

	while(c < '0' || c > '9') c = gc;

	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc;

	return x * f ;

}

void print(int x) {

	if(x >= 10 ) print(x / 10);

	pc(x % 10 + '0');

}

int n;

const int mod = 1e9 + 7;

inline int fstpow(int x,int k ){

	int ret = 1;

	for(;k;k >>= 1,x = 1ll * x * x % mod)

		if(k & 1) ret = 1ll * ret * x % mod;

	return ret;

} 

const int maxn = 25001;

int a[200006],b[200007];

int jc[(maxn << 2)],inv[(maxn << 2) + 7];

inline int C(int x,int y) {

	return 1ll * jc[x] * inv[y] % mod * inv[x - y]% mod;

}

int main() {

	n = read();

	int ans = 0;

	for(int i = 1;i <= n;++ i) {

		a[i] = read(),b[i] = read();

	}

	for(int i = 1;i < (maxn << 1);++ i)

		for(int j = 1;j <= (maxn << 1);++ j)

	for(int i = 1;i <= n;++ i) {

	} 

	jc[0] = jc[1] = 1;

	for(int i = 2;i < (maxn << 2); ++ i) jc[i] = 1ll * jc[i - 1] * i % mod;  

	inv[(maxn << 2) - 1] = fstpow(jc[(maxn << 2) - 1],mod - 2);

	print(fstpow(jc[500000],mod - 2));

	for(int i = (maxn << 2) - 2;i;-- i)  inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;

	for(int i = 1;i <= n;++ i) {

		ans = ((ans - C(a[i] * 2 + b[i] * 2,a[i] * 2)) % mod + mod) % mod;

	}

	ans = (1ll * 500000004 * ans) % mod;

	print(ans);

	return 0;

}

AGC001 E - BBQ Hard 组合数学的相关教程结束。