UVa 12316 - Sewing Buttons with Grandma

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

有 N 種不同顏色的鈕扣,每一種燈泡分別有 $n_{i}$ 個,請問拿 M 個鈕扣獲得的組合類型有多少種。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
1 3
3
1
1
3 2
4
2
3 2
1
1
0 0

Sample Output

1
2
3
3
7
0

Solution

組合問題,相當於計算以下式子的整數解。

$$x_{1} + x_{2} + x_{3} + .. + x_{n} = M \\ 0 \le x_{i} \le n_{i}$$

事實上,利用 dp[i][j] 表示考慮前 i 種湊出 j 個組合數,得到 dp[i][j + k] += dp[i - 1][j] * C[j + 1 + k][k] 加入新種類的鈕扣。

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
36
37
38
39
40
41
import java.util.Scanner;
import java.math.BigInteger;

public class Main {
public static void main(String[] args) {
BigInteger[][] C = new BigInteger[128][128];
for (int i = 0; i < 128; i++)
for (int j = 0; j < 128; j++)
C[i][j] = BigInteger.ZERO;
for (int i = 1; i < 128; i++) {
C[i][0] = BigInteger.ONE;
for (int j = 1; j <= i; j++)
C[i][j] = C[i - 1][j].add(C[i - 1][j - 1]);
}

Scanner cin = new Scanner(System.in);
int n, m;
int[] A = new int[128];
while (cin.hasNext()) {
n = cin.nextInt();
m = cin.nextInt();
if (n + m == 0)
break;
for (int i = 1; i <= m; i++)
A[i] = cin.nextInt();
BigInteger[][] dp = new BigInteger[128][128];
for (int i = 0; i < 128; i++)
for (int j = 0; j < 128; j++)
dp[i][j] = BigInteger.ZERO;
dp[0][0] = BigInteger.ONE;
for (int i = 1; i <= m; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= A[i] && j + k <= n; k++)
dp[i][j + k] = dp[i][j + k].add(dp[i - 1][j]
.multiply(C[j + k + 1][k]));
}
}
System.out.println(dp[m][n]);
}
}
}

附上一個 C++ 的版本,由於沒有使用 BigInteger 而 Wrong Answer.

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> 

long long C[128][128], A[128];
int main() {
for(int i = 1; i < 128; i++) {
C[i][0] = 1;
for(int j = 1; j <= i; j++)
C[i][j] = C[i-1][j] + C[i-1][j-1];
}
int n, m;
while(scanf("%d %d", &n, &m) == 2 && n+m) {
for(int i = 1; i <= m; i++)
scanf("%lld", &A[i]);
long long dp[128][128] = {};

dp[0][0] = 1;
for(int i = 1; i <= m; i++) {
for(int j = 0; j <= n; j++) {
for(int k = 0; k <= A[i] && j + k <= n; k++)
dp[i][j + k] += dp[i - 1][j] * C[j + 1 + k][k];
}
}
printf("%lld\n", dp[m][n]);
}
return 0;
}