排列组合[HDU1521]

时间:2022-02-13 11:44:47

排列组合

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1736    Accepted Submission(s): 726

Problem Description
有n种物品,并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B,并且数量都是1,从中选2件物品,则排列有"AB","BA"两种。

Input
每组输入数据有两行,第一行是二个数n,m(1<=m,n<=10),表示物品数,第二行有n个数,分别表示这n件物品的数量。

Output
对应每组数据输出排列数。(任何运算不会超出2^31的范围)

Sample Input
2 2
1 1

Sample Output
2

Author
xhd

Recommend
xhd

A typical application of exponential generating function.The i-th good's generating function is (1+x/1!+x^2/2!+......+x^C[i]/C[i]!).In the product of the n functions,the coefficient of the item whose index of x is n multiplies n! is the finally answer.

#include<stdio.h>
#include<string.h>
double p[],frac[],tmp[];
int c[];
int n,m;
int main()
{
int n,m,i,j,k;
frac[]=;
for (i=;i<;i++) frac[i]=frac[i-]*i;
while (scanf("%d%d",&n,&m)!=EOF)
{
for (i=;i<=n;i++) scanf("%d",&c[i]);
memset(p,,sizeof(p));
for (i=;i<=c[];i++) p[i]=1.0/frac[i];
for (i=;i<=n;i++)
{
memset(tmp,,sizeof(tmp));
for (j=;j<=m;j++)
for (k=;k<=c[i];k++)
tmp[j+k]+=p[j]*(1.0/frac[k]);
for (j=;j<=m;j++) p[j]=tmp[j];
}
printf("%.0lf\n",p[m]*frac[m]);
}
return ;
}

排列组合[HDU1521]的更多相关文章

  1. 【指数型母函数】hdu1521 排列组合

    #include<cstdio> #include<cstring> using namespace std; int n,m,jiecheng[11]; double a[1 ...

  2. hdu1521 排列组合&lpar;指数型母函数&rpar;

    题意: 有n种物品,并且知道每种物品的数量ki.要求从中选出m件物品的排数.         (全题文末) 知识点: 普通母函数 指数型母函数:(用来求解多重集的排列问题) n个元素,其中a1,a2, ...

  3. hdu1521 排列组合 指数型母函数模板题

    排列组合 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submis ...

  4. 学习sql中的排列组合,在园子里搜着看于是。。。

    学习sql中的排列组合,在园子里搜着看,看到篇文章,于是自己(新手)用了最最原始的sql去写出来: --需求----B, C, F, M and S住在一座房子的不同楼层.--B 不住顶层.C 不住底 ...

  5. &period;NET平台开源项目速览&lpar;11&rpar;KwCombinatorics排列组合使用案例&lpar;1&rpar;

    今年上半年,我在KwCombinatorics系列文章中,重点介绍了KwCombinatorics组件的使用情况,其实这个组件我5年前就开始用了,非常方便,麻雀虽小五脏俱全.所以一直非常喜欢,才写了几 ...

  6. 【原创】开源&period;NET排列组合组件KwCombinatorics使用&lpar;三&rpar;——笛卡尔积组合

           本博客所有文章分类的总目录:本博客博文总目录-实时更新 本博客其他.NET开源项目文章目录:[目录]本博客其他.NET开源项目文章目录 KwCombinatorics组件文章目录: 1. ...

  7. 【原创】开源&period;NET排列组合组件KwCombinatorics使用&lpar;二&rpar;——排列生成

           本博客所有文章分类的总目录:本博客博文总目录-实时更新 本博客其他.NET开源项目文章目录:[目录]本博客其他.NET开源项目文章目录 KwCombinatorics组件文章目录: 1. ...

  8. 【原创】开源&period;NET排列组合组件KwCombinatorics使用&lpar;一&rpar;—组合生成

           本博客所有文章分类的总目录:本博客博文总目录-实时更新 本博客其他.NET开源项目文章目录:[目录]本博客其他.NET开源项目文章目录 KwCombinatorics组件文章目录: 1. ...

  9. &lbrack;leetcode&rsqb; 题型整理之排列组合

    一般用dfs来做 最简单的一种: 17. Letter Combinations of a Phone Number Given a digit string, return all possible ...

随机推荐

  1. fstream文件操作

    fstream(const char* filename, ios::openmode); ios::app: 以追加的方式打开文件 ios::ate: 文件打开后定位到文件尾,ios:app就包含有 ...

  2. Java语言的编写规范

    ,区别大小写.2,注意编程格式,比如对齐啊 什么的.3,注释一定要写好,有统一的// 或者/* */,这样让程序好看.4,定义变量的时候竟让别人看明白,不要A 啊B 啊什么的 要用英语单词这类的,简而 ...

  3. Judge

    1. 循环list中的所有元素然后删除重复 public   static   List  removeDuplicate(List list)  { for  ( int  i  =   0 ; i ...

  4. linux awk命令详解(转)

    http://www.cnblogs.com/ggjucheng/archive/2013/01/13/2858470.html 简介 awk是一个强大的文本分析工具,相对于grep的查找,sed的编 ...

  5. DRUID连接池的简单使用

    DRUID——为监控而生的DB池 1.  DRUID介绍 DRUID是阿里巴巴开源平台上一个数据库连接池实现,它结合了C3P0.DBCP.PROXOOL等DB池的优点,同时加入了日志监控,可以很好的监 ...

  6. 微信小程序开发

    一.基本的准备工作 1.工具安装 工具是有微信官方提供. 2.下载地址: windows32位:https://servicewechat.com/wxa-dev-logic/download_red ...

  7. Kinect v2&lpar;Microsoft Kinect for Windows v2 &rpar;配置移动电源解决方案

    Kinect v2配置移动电源解决方案 Kinect v2如果用于移动机器人上(也可以是其他应用场景),为方便有效地展开后续工作,为其配置移动电源是十分必要的. 一.选择移动电源 Kinect v2原 ...

  8. python类的成员

    一.实例变量:简单的来说就是给对象赋值 class Person: def __init__(self, name, card_no, height, weight, address, laopo): ...

  9. SpringMVC请求体参数处理问题

    如果请求定义为application/json格式,则要用Spring MVC中@RequestBody参数才能接受(用@RequestParam参数接受会报400错误),但SpringMVC的@Re ...

  10. iOS - 抖音效果

    抖音的转场动画—iOS https://www.jianshu.com/p/29b0165de712 抖音的上下滑实现—iOS https://www.jianshu.com/p/e8799510c7 ...