Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://acm.hdu.edu.cn/showproblem.php?pid=1521
题意：有n种物品，并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有"AB",“BA"两种。
思路：指数型母函数。 对于相同的元素，需要去掉该元素的重复度，即为元素个数的阶乘。具体做法是用double类型存储（方案数除以重复度），然后在最后把阶乘乘回来四舍五入取整（为什么是四舍五入？）
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月27日 星期六 19时48分31秒
4File Name :code/hdu/1521.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33double a[15],tmp[15],f[15];
34int n,m;
35int num[15];
36void pre()
37{
38 f[0] = 1.0;
39 for ( int i = 1 ;i <= 11 ; i++)
40 {
41 f[i] = f[i-1]*i*1.0;
42 }
43}
44int main()
45{
46 #ifndef ONLINE_JUDGE
47 freopen("code/in.txt","r",stdin);
48 #endif
49
50 pre();
51 while (scanf("%d %d",&n,&m)!=EOF)
52 {
53 for ( int i = 1 ; i <= n ; i++) scanf("%d",&num[i]);
54
55 ms(a,0);
56 ms(tmp,0);
57
58 for ( int i = 0 ; i <= num[1] ; i++)
59 {
60 a[i] = 1.0/f[i];
61 }
62
63 for ( int i = 2 ; i <= n ; i++)
64 {
65 for ( int j = 0 ; j <= m ; j++)
66 {
67 for ( int k = 0 ; k+j<=m&&k<=num[i] ; k++)
68 {
69 tmp[j+k] += a[j]/f[k];
70 }
71 }
72
73 for ( int j = 0 ; j <= m ; j++)
74 {
75 a[j] = tmp[j];
76 tmp[j] = 0.0;
77 }
78 }
79
80 double ans = a[m]*f[m];
81 printf("%d\n",int(ans+0.5));
82 }
83
84 #ifndef ONLINE_JUDGE
85 fclose(stdin);
86 #endif
87 return 0;
88}