hdu 1521

向右看齐 2023-02-27 05:37 25阅读 0赞

![博客图片][format_png]

## 题目链接 ##

[hdu1521][]

## 题目概述 ##

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

## 解题思路 ##

指数型母函数的概念题,<组合数学>这本书中有一个定理: 
 S = \{ n 1 a 1 , n 2 a 2 , … , n k a k \} ,   ( n i = 1 , 2 , 3 , … , i = 1 , 2 , 3 , … , k ) T h e   e x p o n e n t i a l   g e n e r a t i n g   f u n c t i o n   g ( e ) ( x )   o f   t h e   s e q u e n c e   h 0 , h 1 , h 2 , ⋯   , h n , ⋯   ,   i s   g i v e n   b y : g ( e ) = f n 1 ( x ) f n 2 ( x ) ⋯ f n k ( x ) f n i = 1 + x + x 2 2 ! + ⋯ + x n i n i !   ( i = 1 , 2 , ⋯   , k ) 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) S=\{ n1a1,n2a2,…,nkak\},(ni=1,2,3,…,i=1,2,3,…,k)Theexponentialgeneratingfunctiong(e)(x)ofthesequenceh0,h1,h2,⋯,hn,⋯,isgivenby:g(e)=fn1(x)fn2(x)⋯fnk(x)fni=1\+x\+2!x2\+⋯\+ni!xni(i=1,2,⋯,k)

很明显这个题就是上面定理的概念题,已知 a i a\_i ai和 n i n\_i ni,计算 m m m排列的个数.

下面的表格给出了一次计算的过程:  
下面通过这个表格给出计算 ( 1 + x 1 1 ! + x 2 2 ! ) ( 1 + x 1 1 ! + x 2 2 ! + x 3 3 ! ) (1+\\frac\{x^1\}\{1!\}+\\frac\{x^2\}\{2!\})(1+\\frac\{x^1\}\{1!\}+\\frac\{x^2\}\{2!\}+\\frac\{x^3\}\{3!\}) (1\+1!x1\+2!x2)(1\+1!x1\+2!x2\+3!x3)的计算过程:  
**(表格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 x^i xi的变化的`j`每一步的增长是一步,可以从上面的定理中看出.

## 其它 ##

[format_png]: /images/20230209/560a631bf7d9448b94b9018e38e7282e.png
[hdu1521]: http://acm.hdu.edu.cn/showproblem.php?pid=1521