解題區/解題區 - UVa

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;
}