Divide and Count
题目大意:给定箱子的数量和每个箱子的容量,在每个箱子里都装满对应容量的宝石,每颗宝石都是独一无二的,求一共有多少种放置方式。但是如果两个箱子的容量相同,则认为是 同一种箱子
Sample input:
2
3 3
3
1 2 3
Sample output:
10
60
分析:这是练习赛的时候处在HUST上的题目,当时感觉代码完全对了,却坑了半天,看了题解才发现,是最后除以相同的箱子的时候,是除以它的数量的阶乘,本来是这么想的,却先把它们给乘起来了,样例只是碰巧对而已。也用不到64位整数。
代码如下:
#include <iostream>
# include<cstdio>
# include<cstring>
using namespace std; int f(int a,int b) //从a到b的乘积
{
int i;
int ans= ;
for(i=a; i<=b; i++)
{
ans *= i;
}
return ans;
}
int main()
{
int i,T,sum,hh,ans;
int num[],a[];
while(scanf("%d",&T)!=EOF)
{ sum = ;
for(i=; i<=; i++)
a[i]=;
for(i=; i<T; i++)
{
scanf("%d",&num[i]);
a[num[i]]++;
sum += num[i];
}
ans =;
for(i=; i<T; i++)
{
ans *= f(sum-num[i]+,sum)/f(,num[i]);
sum -= num[i];
}
for(i=; i<=; i++)
{
if(a[i]>)
ans /= f(,a[i]); //这里除以阶乘
}
printf("%d\n",ans);
}
return ;
}