本文主要是介绍HLJUOJ1127 HDU2049(错排公式+排列组合)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1127: 递推求解专题练习二
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 20 Solved: 8
[ Submit][ Status][ Web Board]
Description
在电影院看电影时，总会有观众坐错座位号的情况。现在正在首播的青春爱情喜剧悬疑科幻大片《来治猩猩的你》观影现场爆满(满席)。
那么问题来了，假设座位数为N和坐错座位号的观众人数为M，要求你编写程序求出出现这种情况一共有多少种可能。
Input
输入数据的第一行是一个整数T,表示测试实例的个数，
然后是T行数据，每行包含两个整数N和M(1<M<=N<=20)。
Output
对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。
Sample Input
2
2 2
3 2
Sample Output
1
3
HINT
注意数据范围是否有溢出，本oj建议用long long和%lld。
解题思路：
首先n个座位，m人坐错，那么就有m个错排，因为每个人坐错的概率是相等的，所以用组合数C（n , m）求出做错的人数。最后C( n , m) * d[ m ]
错排公式是如何推得的：
当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用D(n)表示，那么D(n-1)就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推.
第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；
第二步，放编号为k的元素，这时有两种情况：⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种方法；⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有D(n-1)种方法；
综上，d[ i ] = ( i -1 ) * (d[i - 1] + d[ i - 2])；
这道题虽然和hdu上的思路一样，但是经过测试，hdu上的数据范围应该不止20，因为计算组合数那出了偏差，20以内的组合数计算的确是没问题的，但是超过20后就不同了。普通的n!/(m! * (n - m) !)会出问题，所以换一种巧妙地求解组合数的方法。把n!和(n - m)! 进行约分为S1，m!计算S2，最后S1 / S2即可。
完整代码：
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")
typedef __int64 LL;
//typedef long long LL;
typedef double DB;
typedef unsigned uint;
typedef unsigned long long uLL;/** Constant List .. **/ //{const int MOD = int(1e9)+7;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const DB EPS = 1e-9;
const DB OO = 1e20;
const DB PI = acos(-1.0); //M_PI;int n , m;const int maxn = 100001;
LL d[maxn];/*
LL f(int x)
{LL sum = 1;for(int i = 1 ; i <= x ; i ++){sum *= i;}return sum;
}
*//*
LL f(int x)
{*//*if(n == m)return 1;if(m == 1)return n;return f(n - 1 , m - 1) + f(n - 1 , m);*//* LL sum = 1;for(int i = 1; i <= x ; i ++)sum *= i;return sum ;
}*/__int64 C(int n,int m)
{int i;__int64 s1=1,s2=1;for(i=1;i<=m;i++){s1*=(n-i+1);s2*=i;}return s1/s2;
}int main()
{#ifdef DoubleQfreopen("in.txt","r",stdin);#endifint T;scanf("%d",&T);d[0] = 0;d[1] = 0;d[2] = 1;for(int i = 3; i < maxn; i ++){d[i] = (i - 1) * (d[i - 1] + d[i - 2]);}while(T--){scanf("%d%d",&n,&m);// LL cnt1 = f(n);// LL cnt2 = f(m);// LL cnt3 = f(n - m);// LL res = (LL)(cnt1 / (double)cnt2 * cnt3);printf("%I64d\n", C(n , m) * d[m]);}
}这篇关于HLJUOJ1127 HDU2049(错排公式+排列组合)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
