高中知识,求全排列组合后,去重方法是除以相同物品的数量阶乘。那么如果我们再构造母函数的时候,就把阶乘作为每一项的分母,那求出来就可以直接乘上全排列系数了。
//// main.cpp// HDU4333//// Created by teddywang on 16/3/9.// Copyright © teddywang. All rights reserved.//#include <iostream>#include<cstdio>#include<cstring>#include<algorithm>#define LL long longusing namespace std;const LL N = 13;int lim[N];double dp[2][N];LL fac[N];double solve(int n,int m){fac[0] = 1;for (LL i = 1, f = 1; i < N; i++)f*=i,fac[i] = f;fill(dp[0], dp[0] + m + 1, 0);fill(dp[1], dp[1] + m + 1, 0);dp[0][0] = 1;for (int i = 0; i < n; i++){for (int j = 0; j <= lim[i]; j++){for (int k = 0; k + j <= m; k++){dp[1][k + j] += dp[0][k]*1.0 / fac[j];}}for (int j = 0; j <= m; j++)dp[0][j] = dp[1][j], dp[1][j] = 0;}return dp[0][m]*fac[m];}int main(){cin.sync_with_stdio(false);int n, m;while (scanf("%d%d",&n,&m)!=EOF){for (int i = 0; i < n; i++)scanf("%d", &lim[i]);printf("%.0f\n", solve(n,m));}}