[组合数学]取石子

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

取石子

题目描述

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

输入描述:

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

输出描述:

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

输入

1
3 5 4 2

输出

1
2522520

备注:

输入均为不超过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)。

暴力枚举

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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了一下。

1
2
3
4
5
6
7
8
9
10
11
12
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),这样把除法转化成加法,就可以模运算了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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)模板
1
2
3
4
5
6
7
8
9
10
11
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;
}
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!