题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2049

题目描述

给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;

然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.

最后,揭开盖头,如果找错了对象就要当众跪搓衣板…

看来做新郎也不是容易的事情…

假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.

思路

这题错排,和前面的那题错排问题差不多,具体分析可看错排

AC代码

/*************************************************************************
    > File Name: 2049.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Fri 29 May 2015 12:03:32 AM CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
const long long fac[21]={1,1,2,6,24,120,720,5040,40320,362880,
                        3628800,39916800,479001600,6227020800,
                        87178291200,1307674368000,20922789888000,
                        355687428096000,6402373705728000,121645100408832000,
                        2432902008176640000};
long long C(int n, int m) {
    return fac[n]/fac[m]/fac[n-m];
}

int main()
{
#ifdef Oj
#endif
    long long D[21][21]; // D[N][M]表示N个人中有M个选错新娘的种数
    D[1][1] = 0;
    D[2][2] = 1;
    for(int i=3; i<=20; ++i)
        D[i][i] = (i-1)*(D[i-1][i-1] + D[i-2][i-2]); // 错排公式,N个人都选错新娘的总数
    for(int n=1; n<=20; ++n)
        for(int m=1; m<n; ++m) 
            D[n][n-m] = C(n, m)*D[n-m][n-m]; // 公式C(n, m)*D[n-m][n-m]表示n个人中有m个选对了新娘,那么n-m就是选错新娘的人数,即D[n][n-m]
    int T;
    cin >> T;
    while(T--) {
        int n, m;
        cin >> n >> m;
        cout << D[n][m] << endl;
    }
    return 0;
}