不容易系列之(4)——考新郎 （hdu 2049）_不容易系列之4-程序员宅基地
技术标签： dp
国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的:
首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;
然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.
最后,揭开盖头,如果找错了对象就要当众跪搓衣板...
看来做新郎也不是容易的事情...
假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.
Input
输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1<M<=N<=20)。
Output
对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。
Sample Input
2
2 2
3 2Sample Output
1
3题解：就是从m个元素中选出n个进行错排，错排推导之前有写过，就不推导了，直接引用，dp[n]=(n-1)*(dp[n-1]+dp[n-2])，注意最后输出时要先除再乘，否则会爆long long的。
代码如下：
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <ctime>
#define maxn 10007
#define N 107
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define lowbit(x) (x&(-x))
#define eps 0.00000001
using namespace std;
typedef long long ll;
int main()
{
long long int dp[31];
dp[0]=0;
dp[1]=1;
dp[2]=1;
dp[3]=2;
for(int i=4; i<=20; i++)
dp[i]=(i-1)*(dp[i-1]+dp[i-2]);
int t;
cin>>t;
while(t--)
{
int m,n;
long long int s1=1,s2=1,s3=1;
cin>>m>>n;
for(int i=1;i<=m;i++)
s1*=i;
for(int i=1;i<=n;i++)
s2*=i;
for(int i=1;i<=m-n;i++)
s3*=i;
cout<<s1/s2/s3*dp[n]<<endl;
}
return 0;
}
智能推荐
React学习记录-程序员宅基地
文章浏览阅读936次，点赞22次，收藏26次。React核心基础
Linux查磁盘大小命令,linux系统查看磁盘空间的命令是什么-程序员宅基地
文章浏览阅读2k次。linux系统查看磁盘空间的命令是【df -hl】，该命令可以查看磁盘剩余空间大小。如果要查看每个根路径的分区大小，可以使用【df -h】命令。df命令以磁盘分区为单位查看文件系统。本文操作环境：red hat enterprise linux 6.1系统、thinkpad t480电脑。(学习视频分享：linux视频教程)Linux 查看磁盘空间可以使用 df 和 du 命令。df命令df 以磁..._df -hl
Office & delphi_range[char(96 + acolumn) + inttostr(65536)].end[xl-程序员宅基地
文章浏览阅读923次。uses ComObj;var ExcelApp: OleVariant;implementationprocedure TForm1.Button1Click(Sender: TObject);const // SheetType xlChart = -4109; xlWorksheet = -4167; // WBATemplate xlWBATWorksheet = -4167_range[char(96 + acolumn) + inttostr(65536)].end[xlup]
若依 quartz 定时任务中 service mapper无法注入解决办法_ruoyi-quartz无法引入ruoyi-admin的service-程序员宅基地
文章浏览阅读2.3k次。上图为任务代码，在任务具体执行的方法中使用，一定要写在方法内使用SpringContextUtil.getBean()方法实例化Spring service类下边是ruoyi-quartz模块中util/SpringContextUtil.java(已改写)import org.springframework.beans.BeansException;import org.springframework.context.ApplicationContext;import org.s..._ruoyi-quartz无法引入ruoyi-admin的service
CentOS7配置yum源-程序员宅基地
文章浏览阅读2w次，点赞10次，收藏77次。yum，全称“Yellow dog Updater, Modified”，是一个专门为了解决包的依赖关系而存在的软件包管理器。可以这么说，yum 是改进型的 RPM 软件管理器，它很好的解决了 RPM 所面临的软件包依赖问题。yum 在服务器端存有所有的 RPM 包，并将各个包之间的依赖关系记录在文件中，当管理员使用 yum 安装 RPM 包时，yum 会先从服务器端下载包的依赖性文件，通过分析此文件从服务器端一次性下载所有相关的 RPM 包并进行安装。_centos7配置yum源
智能科学毕设分享(算法) 基于深度学习的抽烟行为检测算法实现(源码分享)-程序员宅基地
文章浏览阅读828次，点赞21次，收藏8次。今天学长向大家分享一个毕业设计项目毕业设计 基于深度学习的抽烟行为检测算法实现(源码分享)毕业设计 深度学习的抽烟行为检测算法实现通过目前应用比较广泛的 Web 开发平台，将模型训练完成的算法模型部署，部署于 Web 平台。并且利用目前流行的前后端技术在该平台进行整合实现运营车辆驾驶员吸烟行为检测系统，方便用户使用。本系统是一种运营车辆驾驶员吸烟行为检测系统，为了降低误检率，对驾驶员视频中的吸烟烟雾和香烟目标分别进行检测，若同时检测到则判定该驾驶员存在吸烟行为。进行流程化处理，以满足用户的需要。
随便推点
STM32单片机示例：多个定时器同步触发启动_stm32 定时器同步-程序员宅基地
文章浏览阅读3.7k次，点赞3次，收藏14次。多个定时器同步触发启动是一种比较实用的功能，这里将对此做个示例说明。_stm32 定时器同步
android launcher分析和修改10,Android Launcher分析和修改9——Launcher启动APP流程（转载）...-程序员宅基地
文章浏览阅读348次。出处 : http://www.cnblogs.com/mythou/p/3187881.html本来想分析AppsCustomizePagedView类，不过今天突然接到一个临时任务。客户反馈说机器界面的图标很难点击启动程序，经常点击了没有反应，Boss说要优先解决这问题。没办法，只能看看是怎么回事。今天分析一下Launcher启动APP的过程。从用户点击到程序启动的流程，下面针对WorkSpa..._回调bubbletextview
Ubuntu 12 最快的两个源 个人感觉 163与cn99最快 ubuntu安装源下包过慢_un.12.cc-程序员宅基地
文章浏览阅读6.2k次。Ubuntu 12 最快的两个源 个人感觉 163与cn99最快 ubuntu下包过慢 1、首先备份Ubuntu 12.04源列表 sudo cp /etc/apt/sources.list /etc/apt/sources.list.backup （备份下当前的源列表，有备无患嘛） 2、修改更新源 sudo gedit /etc/apt/sources.list （打开Ubuntu 12_un.12.cc
vue动态路由（权限设置）_vue动态路由权限-程序员宅基地
文章浏览阅读5.8k次，点赞6次，收藏86次。1.思路（1）动态添加路由肯定用的是addRouter，在哪用？（2）vuex当中获取到菜单，怎样展示到界面2.不管其他先试一下addRouter找到router/index.js文件，内容如下，这是我自己先配置的登录路由现在先不管请求到的菜单是什么样，先写一个固定的菜单通过addRouter添加添加以前注意：addRoutes()添加的是数组在export defult router的上一行图中17行写下以下代码var addRoute=[ { path:"/", name:"_vue动态路由权限
JSTL 之变量赋值标签-程序员宅基地
文章浏览阅读8.9k次。 关键词： JSTL 之变量赋值标签 /* * Author Yachun Miao * Created 11-Dec-06 */关于JSP核心库的set标签赋值变量，有两种方式: 1.日期" />2. 有种需求要把ApplicationResources_zh_CN.prope
VGA带音频转HDMI转换芯片|VGA转HDMI 转换器方案|VGA转HDMI1.4转换器芯片介绍_vga转hdmi带音频转换器,转接头拆解-程序员宅基地
文章浏览阅读3.1k次，点赞3次，收藏2次。1.1ZY5621概述ZY5621是VGA音频到HDMI转换器芯片，它符合HDMI1.4 DV1.0规范。ZY5621也是一款先进的高速转换器，集成了MCU和VGA EDID芯片。它还包含VGA输入指示和仅音频到HDMI功能。进一步降低系统制造成本，简化系统板上的布线。ZY5621方案设计简单，且可以完美还原输入端口的信号，此方案设计广泛应用于投影仪、教育多媒体、视频会议、视频展台、工业级主板显示、手持便携设备、转换盒、转换线材等产品设计上面。1.2 ZY5621 特性内置MCU嵌入式VGA_vga转hdmi带音频转换器,转接头拆解