hdu2049 不容易系列之(4)——考新郎(组合,错排)
2024-09-04 11:45:54
题意:
n 个数中 m 个数错排的情况个数。
思路:
先从 n 个数中选出 m 个,即 $C_n^m$,
再算出 m 个数的错排数,即 ${f_{\left( m \right)}}$。
错排:
当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用f(n)表示,那么f(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推
第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法
第二步,放编号为k的元素,这时有两种情况
( 1 ) 把它放到位置n,那么,对于剩下的n-1个元素,由于第k个元素放到了位置n,剩下n-2个元素就有f(n-2)种方法;
( 2 ) 第k个元素,不把它放到位置n,这时,对于这n-1个元素,有f(n-1)种方法;
综上得到:f (n) = (n-1)*( f(n-2) + f(n-1) )
特殊地,f (1) = 0, f (2) = 1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; ll c[25][25],f[25]={0,0,1}; void Init(){
for(int n=0;n<=20;n++)//Cn 0和Cn n都置为1
c[n][0]=c[n][n]=1;
for(int n=1;n<=20;n++)//Cn 1到Cn n-1由递推公式求得
for(int m=1;m<n;m++)
c[n][m]=c[n-1][m-1]+c[n-1][m];
for(int i=3;i<=20;i++)//规模为i的错排的递推
f[i]=(i-1)*(f[i-1]+f[i-2]);
} int main()
{
Init();//初始化组合、错排表
ll t,n,m;cin>>t;
while(t--){
cin>>n>>m;
cout<<c[n][m]*f[m]<<endl;
}
return 0;
}
参考博客:Hdu 2049解题报告
最新文章
- solr 日期查询格式
- AC日记——判断字符串是否为回文 openjudge 1.7 33
- <;fieldset>;
- linux文件上传,给文件或目录添加apache权限
- Debugging Process Startup
- HttpSendRequest同步请求不返回
- SVG 路径(path)
- iOS开展UI一片—简单的浏览器观看节目
- 字符编码知识:Unicode、UTF-8、ASCII、GB2312等编码之间是如何转换的?
- 对Spring from中日期显示格式化问题
- oracle查看经常使用的系统信息
- 手机摄像头扫描识别车牌号,移动端车牌识别sdk
- PHP SPL迭代模式
- 数据库之mac上mysql root密码忘记或权限错误的解决办法
- Web自动化框架LazyUI使用手册(7)--浏览器常用操作API
- jvm 年轻代、年老代、永久代
- 【leetcode】53-MaximumSubarray
- VC6.0支持UNICODE的步骤
- JavaScript对象参考手册
- FromBottomToTop团队项目总结
热门文章
- readhat6.5下安装weblogic10.3.6
- N叉树的最大深度-DFS
- requests+BeautifulSoup | 爬取电影天堂全站电影资源
- SQL中的主键,候选键,外键,主码,外码
- 关联实现上-jsonpath取值
- 【MYSQL】win7安装mysql-5.7.10绿色版
- Python3.9的http.client.py下的HTTPMessage类中的方法getallmatchingheaders的bug修复建议
- Linux操作系统相关资料
- mysql5.5 升级至5.7
- centos7+宝塔+ssrpanel v3 魔改版 前后端配置教程