wwx0848的专栏

HDU 1521 排列组合

题意 （中文） 思路 此题是一道指数型母函数的题目， G(x) = (1 + x / 1! + x^2 / 2！ + x^3 / 3! + …. + x^n1 / n1!) * (1 + x / 1 ! + x^2 / 2! + … + x^n2 / n2!) * … * (1 + x / 1! + x^2 / 2! + .. + x^nk / nk!). 先把阶层求出来，，当计算的时候每次都除f[n],在最后还原系数的时候再乘上去。 Code

const int MAX = 2e9;const int MIN = -2e9;const double eps = 1e-8;const double PI = acos(-1.0);;const int N = 100;int f[N];int a[N];double c1[N], c2[N];void init(){f[0] = 1;for(int i = 1; i <= 13; ++i){f[i] = f[i – 1] * i;}}int main(){int n, m;init();while(~scanf(“%d%d”, &n, &m)){for(int i = 1; i <= n; ++i){scanf(“%d”, &a[i]);}Mt(c1, 0);Mt(c2, 0);c1[0] = 1;for(int i = 1; i <= n; ++i){for(int k = 0; k <= a[i]; ++k){for(int s = 0; s + k <= m; ++s){c2[s + k] += c1[s] / f[k];}}for(int k = 0; k <= m; ++k){c1[k] = c2[k];c2[k] = 0;}}printf(“%.0f\n”, c1[m] * f[m]);}return 0;}

命运如同手中的掌纹，无论多曲折，终掌握在自己手中。