Problem B
Combinations, Once Again
Input: Standard Input

Output: Standard Output

Time Limit: 2 Seconds

Given n objects you'd have to tell how many different groups can be chosen if r objects are taken at a time.

Input 

Input consists of 100 test cases. Each test case begins with two integers n (0 < n <= 50), m (0 <= m <= n). The next line will contain the labels (numbers in the range 1 to n) of the n objects you are to choose from.  Two objects with the same label are considered equivalent. Then in the last line for that test case, you'd have m values for r. There will be a single space separating two consecutive numbers in a line. Input is terminated by a test case where n=0, you must not process this test case.

Output 

For each test case, print the test case number. And for each query number r, print the number of different groups that can be formed if r objects are taken from the given n objects. You can assume that for all input cases, the output will always fit in a 64-bit unsigned integer and (0<=r<=n).

Sample Input                             Output for Sample Input

5 2

1 2 3 4 5

2 1

4 1

1 2 3 4 

2

0 0

Case 1:

10

5

Case 2:

Problemsetter: Monirul Hasan, Member of Elite Problemsetters' Panel

重複組合。

dp[放入的種類][個數] = 方法個數

#include <stdio.h>

int main() {
    int n, m, x, i, j, k, r, cases = 0;
    while(scanf("%d %d", &n, &m) == 2 && n) {
        int label[150] = {};
        for(i = 0; i < n; i++)
            scanf("%d", &x), label[x]++;
        printf("Case %d:\n", ++cases);
        while(m--) {
            scanf("%d", &r);
            long long dp[100][100] = {};
            dp[0][0] = 1;
            for(i = 1; i <= n; i++) {
                for(j = 0; j <= r; j++)
                    dp[i][j] = dp[i-1][j];
                for(j = 0; j <= r; j++) {
                    for(k = 1; k <= label[i] && j+k <= r; k++) {
                        dp[i][j+k] += dp[i-1][j];
                    }
                }
            }
            printf("%lld\n", dp[n][r]);
        }
    }
    return 0;
}