字串数
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4794 Accepted Submission(s): 1275
Problem Description
一个A和两个B一共可以组成三种字符串:"ABB","BAB","BBA".
给定若干字母和它们相应的个数,计算一共可以组成多少个不同的字符串.
Input
每组测试数据分两行,第一行为n(1<=n<=26),表示不同字母的个数,第二行为n个数A1,A2,...,An(1<=Ai<=12),表示每种字母的个数.测试数据以n=0为结束.
Output
对于每一组测试数据,输出一个m,表示一共有多少种字符串.
Sample Input
2
1 2
3
2 2 2
0
Sample Output
3
90
Source
浙江工业大学第四届大学生程序设计竞赛
Recommend
JGShining | We have carefully selected several similar problems for you:
1263
1265
1264
1262
1260
组合公式为（A1+A2+...+An）!/A1!/A2!/.../An!
显然是要用到大数乘除法了，我用的是100000进制，节约一下内存空间。。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mod = 1e5;
const int maxn = 200;
int n,ans,i,j,k,t,len;
int a[30],num[maxn];
int main(){
while (scanf("%d",&n) && n) {
ans = 0;
for (i=0; i<n; i++) {
cin >> a[i];
ans += a[i];
}
memset(num,0,sizeof(num));
num[0] = 1;
len = 1;
for (i=2; i<=ans; i++) {
int x = 0;
for (k=0; k<len; k++) {
num[k] *= i;
num[k] += x;
x = 0;
if (num[k]>mod) {
x = num[k]/mod;
num[k] %= mod;
}
}
if (x!=0) num[len++] = x;
}
for (i=0; i<n; i++) {
for (j=2; j<=a[i]; j++) {
int x = 0, y = 0;
for (k =len -1; k>=0; k--) {
y = x;
x = (num[k]+ y*mod)%j;
num[k] = (num[k]+ y*mod)/j;
}
while (num[len-1]==0) len--;
}
}
while (num[len]==0) len--;
printf("%d",num[len]);
for (i=len-1; i>=0; i--) printf("d",num[i]);
printf("\n");
}
return 0;
}
