[组合数学]取石子

为什么要写关于这道题的博客呢？首先本题本人用python成功ac，要知道很少有人用Python做算法题。而且本人已经好几个月没用Python了，所以记录一下。此外，本题用到了排列组合打表，整理好代码，以后要用模板就不用再找了。

取石子

题目描述

给出四堆石子，石子数分别为a,b,c,d。规定每次只能从堆顶取走石子，问取走所有石子的方案数。

输入描述:

1	在一行内读入四个由空格分隔的整数a,b,c,d，输入均为不超过500的正整数

输出描述:

1	输出一个整数表示答案，答案对109+7取模

输入

3 5 4 2

输出

备注:

输入均为不超过500的正整数

题解：

我们一堆一堆的考虑。第一堆a，第2堆b，第3堆c，第4堆d。假如只有一堆，则只有1种情况，即C(a,a)。假如有两堆，我们可以当做这两堆石子的排列组合。可以算出两堆石子的方案数。即C(b,a+b)。第三堆我们可以把前两堆看成一堆，然后继续排列组合，即C(c,a+b+c)。第4队即C(d,a+b+c+d)。最后全部相乘即可，即C(a,a) C(b,a+b) C(c,a+b+c)*C(d,a+b+c+d)。

暴力枚举

首先想到暴力枚举，虽然一定超时。以下是代码。只需要把所有情况列一遍即可。

#include<stdio.h>
#define ll long long
ll a[4];
ll cnt = 0;
void dfs(ll a, ll b, ll c, ll d) {
	if (!a&&!b&&!c&&!d) {
		cnt++;
		cnt %= 1000000000 + 7;
		return;
	}
	if (a)
		dfs(a - 1, b, c, d);
	if (b)
		dfs(a, b - 1, c, d);
	if (c)
		dfs(a, b, c - 1, d);
	if (d)
		dfs(a, b, c, d - 1);
}
int main() {
	for (int i = 0; i < 4; i++)
		scanf("%lld", &a[i]);
	dfs(a[0], a[1], a[2], a[3]);
	printf("%lld\n", cnt);
	return 0;
}

python

由于数据过大，c++没有大数类，所以用python首先A了一下。

f = input().split()
ans = 1
sum = [int(f[0]),0,0,0]
for i in range(1,4):
    sum[i]=sum[i-1]+int(f[i])
    for j in range(sum[i]-int(f[i])+1,sum[i]+1):
        ans*=j
for i in range(1,4):
    for j in range(1,int(f[i])+1):
        ans//=j
ans%=1000000007
print(ans)

c++

由于acm不能用python，所以只能再考虑c++。首先由于涉及到除法，所以不能直接取余。

我没知道公式：C(M,N)=C(M-1,N)+C(M-1，N-1)，这样把除法转化成加法，就可以模运算了。

#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int maxn = 501;
const ll mod = 1000000007;
ll a[4], sum[4] = { 0 };
ll dp[maxn * 4][maxn * 4];
void init() {
	dp[0][0] = 0;
	for (int i = 1; i < 4 * maxn; i++) {
		dp[i][0] = 1;
		for (int j = 1; j < i; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
			dp[i][j] %= mod;
		}
		dp[i][i] = 1;
	}
}
int main() {
	init();
	ll ans = 1;
	for (int i = 0; i < 4; i++) {
		!i ? sum[i] = 0 : sum[i] = sum[i - 1];
		cin >> a[i];
		sum[i] += a[i];
		if (a[i] > sum[i] - a[i]) a[i] = sum[i] - a[i];
	}
	for (int i = 1; i < 4; i++) {
		ans *= dp[sum[i]][a[i]];
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}

C(M,N)模板

void init() {
	dp[0][0] = 0;
	for (int i = 1; i < 4 * maxn; i++) {
		dp[i][0] = 1;
		for (int j = 1; j < i; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
			dp[i][j] %= mod;
		}
		dp[i][i] = 1;
	}
}