AT1983 [AGC001E] BBQ Hard

前言

学到了一个\(trick\)。
对于一个组合数 \(C_{x+y}^x\)可以看成是从\((0,0)\)到\((x,y)\)的路径条数。

解法

对于这题而言，\(C_{a_i+b_i+a_j+b_j}^{a_i+a_j}\)就表示从点\((0,0)\)到点\((a_i+a_j,b_i+b_j)\)的路径条数。
然后你会发现这并没有什么卵用
于是又出现了一个\(trick\)。考虑平移这两个点变成\((-a_i,-b_i)\)和\((a_j,b_j)\)。然后把所有的\((-a_i,-b_i)\)都\(+1\)之后就可以进行一个简单的\(DP\)。

\(dp[i][j]\)表示从某一个出发点到\((i,j)\)的路径条数。把所有\(dp[a[i]][b[i]]\)的答案加起来就是一个初步的答案。由于题目里边要求\(i<j\),所以减去重复的答案然后除以\(2\)，就可以了。重复的答案就是\(C_{2(a_i+b_i)}^{2a_i}\)。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define R register
#define LL long long
const int inf = 0x3f3f3f3f;
const int MAXN = 2e5 + 10;
const int P = 1e9 + 7;
const int MAXM = 5e3 + 10;
const int D = 2e3 + 10;

inline int read() {
	char a = getchar(); int x = 0,f = 1;
	for(; a > '9' || a < '0'; a = getchar()) if(a == '-') f = -1;
	for(; a >= '0' && a <= '9' ;a = getchar()) x = x * 10 + a - '0';
	return x * f;
}

int n;
int a[MAXN], b[MAXN]; 
int f[MAXM][MAXM];
int fac[MAXM * 2], ifac[MAXM * 2];

inline int qpow(int x,int k) {
	int res = 1;
	while(k) {
		if ( k & 1 ) res = 1LL * res * x % P;
		x = 1LL * x * x % P;
		k >>= 1; 
	}
	return res;
}

inline int C(int x, int y) {
	return 1LL * fac[x] * ifac[y] % P * ifac[x - y] % P;
}

int main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n = read(); 
	for(R int i = 1; i <= n ; i++) a[i] = read(), b[i] = read(); 
	for(R int i = 1; i <= n ; i++) f[D - a[i]][D - b[i]] ++;
	
	for(R int i = 1; i <= D * 2; i++) 
		for(R int j = 1; j <= D * 2; j++)
			f[i][j] += ( f[i - 1][j] + f[i][j - 1] ) % P, f[i][j] %= P;
			
	fac[0] = 1;
	for(R int i = 1; i <= D * 4; i++) fac[i] = 1LL * fac[i - 1] * i % P;
	ifac[D * 4] = qpow( fac[D * 4], P - 2 );
	for(R int i = D * 4 - 1; i >= 0 ; i--) 
		ifac[i] = 1LL * ifac[i + 1] * (i + 1) % P;
		
	int ans = 0;
	for ( R int i = 1; i <= n; i++) {
		ans = ( ans + f[D + a[i]][D + b[i]] ) % P;
		ans = ( ans - C ( a[i] * 2 + b[i] * 2, a[i] * 2 ) ) % P;
	}
	
	ans = ( ( ans % P ) + P ) % P;
	printf("%lld\n", 1LL * ans * qpow( 2, P - 2) % P );
	return 0;	
}

这题一个更高端的版本是扩展到三维。式子大概这样的。

看成三维的点去做就可以了。实际上这个式子就可以看成是三维的点之间先选一维的路，在选一维的路。做法同上。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define R register
#define LL long long
const int inf = 0x3f3f3f3f;
const int MAXN = 2e5+10;
const int P = 1e8 + 7;
const int N = 150 + 5;

inline int read() {
	char a = getchar(); int x = 0,f = 1;
	for(; a > '9' || a < '0'; a = getchar()) if(a == '-') f = -1;
	for(; a >= '0' && a <= '9' ;a = getchar()) x = x * 10 + a - '0';
	return x * f;
}

int n;
int a[MAXN], b[MAXN], c[MAXN];
int dp[N * 2 + 1][N * 2 + 1][N * 2 + 1];
int C[N * 6 + 1][N * 6 + 1];

signed main() {
//	freopen("cyj.in","r",stdin);
	//freopen("cyj.out","w",stdout);	
	n = read();
	for(R int i = 1; i <= n; i++) a[i] = read(), b[i] = read(), c[i] = read();
	for(R int i = 1; i <= n; i++) dp[N - a[i]][N - b[i]][N - c[i]]++;
	for(R int i = 1; i <= N * 2; i++)
		for(R int j = 1; j <= N * 2; j++)
			for(R int k = 1; k <= N * 2; k++)
				dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k] + dp[i][j - 1][k] + dp[i][j][k - 1]) % P;
	for(R int i = 0; i <= N * 6; i++) {
		C[i][0] = 1;
		for(R int j = 1; j <= i; j++)
			C[i][j] =( C[i - 1][j] + C[i - 1][j - 1] ) % P;
	}
	int ans = 0;
	for(R int i = 1; i <= n; i++) {
		ans = ( ans + dp[N + a[i]][N + b[i]][N + c[i]] ) ;
		ans = ((ans - 1LL * C[(a[i] + b[i] + c[i]) * 2][a[i] * 2] * C[(b[i] + c[i]) * 2][b[i] * 2]) % P + P) % P ;
	}
	ans = 1LL * ans * (P + 1) / 2 % P; 
	printf("%d\n", ans % P);
	return 0;	
}