Description
Sewing Buttons with Grandma
| Sewing Buttons with Grandma |
After so many years of studying math in the Academy of Colombian Mathematics (ACM) in the tropic, Eloi has finally decided to visit his grandmother for the winter in the north hemisphere. ``Buttons and patches and the cold wind blowing, the days pass quickly when I am sewing‘‘ she says - Eloi now remembers how grandma quilts have love in every stitch. As a matter of fact, he has decided to learn the useful handicraft art of sewing buttons with grandma.
Eloi has realized that there is an interesting mathematical puzzle related to the task of sewing buttons to the front of a shirt. Given a collection of
n1 buttons of color
c1, n2 buttons of color
c2, ..., nk buttons of color
ck, and a shirt with
m front buttonholes, in how many ways the buttonholes can be assigned
m buttons from the n1 +
... + nk buttons?
Input
The input consists of several test cases. The first line of each test case contains two integers
m and k separated by a blank (1
m
50,
1
k
50). Then
k lines follow each containing an integer
ni with 1
ni
50. The last test case is followed by a line containing two zeros.
Output
The output consists of one line per test case containing the number of ways the m buttonholes can be assigned m buttons from the n1 + ... + nk buttons, assuming that the colors c1,..., ck are pairwise distinct.
Sample Input
1 3 3 1 1 3 2 4 2 3 2 1 1 0 0
Sample Output
3 7 0
题意：给你m个纽扣位置，然后有n个不同颜色的重复的纽扣，求组合数
思路：先试着假设f[i][j]表示用i个不同颜色的纽扣组成j个的可能数，那么
f[i][j]=∑i=1n∑j=1m∑k=0a[i]f[i?1][j?k]?C[j][k] 其中 C[j][k] 表示组合数
式子的意思是在i-1的情况下，从j个中挑出k个来放第i个颜色，所以要乘上组合数import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
final int maxn = 105;
int a[] = new int[maxn];
BigInteger f[][] = new BigInteger[maxn][maxn];
BigInteger c[][] = new BigInteger[maxn][maxn];
int n, m;
for (int i = 0; i <= 50; i++) {
c[i][0] = BigInteger.ONE;
c[i][i] = BigInteger.ONE;
}
for (int i = 2; i <= 50; i++)
for (int j = 1; j < i; j++)
c[i][j] = c[i-1][j-1].add(c[i-1][j]);
Scanner in = new Scanner(System.in);
while (true) {
m = in.nextInt();
n = in.nextInt();
if (m == 0 && n == 0)
break;
for (int i = 1; i <= n; i++)
a[i] = in.nextInt();
for (int i = 0; i <= 50; i++)
for (int j = 0; j <= 50; j++)
if (j == 0)
f[i][j] = BigInteger.ONE;
else f[i][j] = BigInteger.ZERO;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 0; k <= a[i]; k++)
if (j - k >= 0)
f[i][j] = f[i][j].add(f[i-1][j-k].multiply(c[j][k]));
System.out.println(f[n][m]);
}
}
}
UVA - 12316 Sewing Buttons with Grandma （有重复元素的组合）,布布扣,bubuko.com