hdu 1521

题目链接

hdu1521

题目概述

        给出 $n$中元素和这些元素的数量,计算选择出 $m$件物品的可能的排列的数目,其中 $(1\leq n,m \leq 10).$

解题思路

        指数型母函数的概念题,<组合数学>这本书中有一个定理:
$S=\{n_1a_1, n_2a_2,\dots,n_ka_k\},\, (n_i=1,2,3,\dots, i=1,2,3,\dots,k)\\The \,exponential \,generating \,function \,g^{(e)}(x)\,of \,the \,sequence \,h_0, h_1, h_2, \cdots, h_n, \cdots, \,is \,given \,by:\\g^{(e)} =f_{n_1}(x)f_{n_2}(x)\cdots f_{n_k}(x)\\f_{n_i} = 1+x+\frac{x^2}{2!}+\cdots+\frac{x^{n_i}}{n_i!} \,(i=1,2,\cdots,k)$

很明显这个题就是上面定理的概念题,已知 $a_i$和 $n_i$,计算 $m$排列的个数.

        下面的表格给出了一次计算的过程:
下面通过这个表格给出计算 $(1+\frac{x^1}{1!}+\frac{x^2}{2!})(1+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!})$的计算过程:
(表格A(上一轮计算的结果))

(表格B(这一轮计算的结果))

(整理之后是这一轮计算的值(对应程序中的temp))

(更新这一轮计算的结果准备计算下一轮(对应程序中的buf))

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 15;
double buf[N];
double temp[N];
ll F[N];
ll nums[N] = {2,3,1};void calculate(int n = 3){fill(buf, buf + N, 0);for (int i = 0;i <= nums[0];i++){buf[i] = 1.0 / F[i];}// for (int i = 0; i < N; ++i){// printf("%.1f ", buf[i]);// }// printf("\n");fill(temp, temp + N, 0);ll sum = nums[0];for (int k = 1; k < n; ++k){for (int i = 0; i <= sum; ++i){for(int j = 0; j <= nums[k]; j++){temp[i + j] += buf[i]/F[j];}}// for (int i = 0; i < N; ++i){// printf("%.0f ", temp[i]*F[i]);// }// printf("\n");memcpy(buf, temp, sizeof(double) * N);fill(temp, temp + N, 0);sum += nums[k];}
}int main(int argc, const char** argv) {F[0] = 1ll;for(int i = 1; i < N; i++){F[i] = F[i - 1] * i;}calculate();int n,m;while (~scanf("%d%d",&n, &m)){for (int i = 0;i < n; ++i){scanf("%lld", &nums[i]);}calculate(n);printf("%.0f\n", buf[m]*F[m]);}return 0;
}

这个程序有以下几点要注意的:

1. 那个sum表示的是已经计算出的最高次项,由当前的元素出现的次数决定;

2. 第二个是因为最后的buf存储的系数实际是除以阶乘之后的,所以要用double来存储,并且在最后输出结果是要再乘以对应的阶乘.

3. 就是这里面表示第二个乘式的 $x^i$的变化的j每一步的增长是一步,可以从上面的定理中看出.

其它