ACM_递推题目系列之二认错人(递推dp)
2024-08-28 21:57:34
Problem Description:
国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的:
首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;
然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.
最后,揭开盖头,如果找错了对象就要当众跪搓衣板...
假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.
Input:
输入数据的第一行是一个整数C,表示测试实例的个数,然后是C行数据,每行包含两个整数N和M(1<M<=N<=20)。
Output:
对于每个测试实例,请输出一共有多少种发生这种情况的可能,每个实例的输出占一行。
Sample Input:
3
3 2
5 3
6 2
Sample Output:
3
20
15
解题思路:简单组合+错排!!!
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL C(int n,int m){
LL ans=;
for(int i=;i<=m;++i)
ans=ans*(n-i+)/i;
return ans;
}
int main(){
LL a[]={,,};
for(int i=;i<;i++)
a[i]=(i-)*(a[i-]+a[i-]);
int c,n,m;
cin>>c;
while(c--){
cin>>n>>m;
cout<<(C(n,m)*a[m])<<endl;
}
return ;
}
最新文章
- 《InsideUE4》-7-GamePlay架构(六)PlayerController和AIController
- Sql Server 中锁的概念
- python多进程提高cpu利用率
- Linux共享库 日志方法
- word size
- C++实现CString和string的互相转换
- yii中阻止 SHOW CREATE TABLE and SHOW COLUMNS 每次执行
- configure文件中判断某函数或库是否存在的一个方法
- Object-C类目(Category)
- VIM大作战之C++简易集成编译环境(Windows篇)
- The package does not support the device architecture (x86). You can change the supported architectures in the Android Build section of the Project Opt
- JavaBean技术的一些讲解
- iOS-模糊查询
- jquery动态加载 去除js
- php会话(session)实现原理
- TortoiseSVN文件夹图标不显示
- 蚂蚁通讯框架SOFABolt之私有通讯协议设计
- Mysql 获取表设计查询语句
- linux文件系統详解
- OK Titlefasdf asd
热门文章
- 不同app之间activity的跳转
- Pagodas 等差数列
- Codeforces 803F(容斥原理)
- ZOJ3953 ZJU2017校赛(贪心)
- Ubuntu 16.04下操作iptables的技巧(解决Failed to start iptables.service: Unit iptables.service not found.或者/etc/init.d/iptables: 没有那个文件或目录)
- Telnet登入cisco router 1800
- 【SSH进阶之路】Hibernate搭建开发环境+简单实例(二)
- 最简单 NDK 样例
- Mesos, Marathon, Docker 平台部署记录
- 【剑指Offer】俯视50题之31 - 40题