HDU 2068 RPG的错排(排列组合，错排)十分详细

HDU 2068 RPG的错排(排列组合，错排)非常详细~

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2068

这道题需要用到错排公式以及高中数学排列组合的知识。

排列组合:【1】排列(从n中拿出m个，并进行排列):A_n_m=n!/(n-m)!=n*(n-1)*(n-2)*........(n-m+1);

                  【2】组合(从n中拿出m个，不进行排列):C_n_m=n!/((n-m)!*m!)=n*(n-1)*(n-2)*........(n-m+1)/(m*(m-1)*.......1);

因此不难得出排列数的代码为:

__<span style="font-size:14px;">int64 A_n_m(int n,int m)
{
    __int64 i,up=1;
    for(i=n;i>=n-m+1;i--)
        up*=i;
    return up;
}</span>

组合数的代码为:

<span style="font-size:14px;">__int64 C_n_m(int n,int m)
{
    __int64 i,up,down;//分子，分母
    up=down=1;
    for(i=n;i>=n-m+1;i--)
        up*=i;
    for(i=m;i>=1;i--)
        down*=i;
    return up/down;
}</span>

递推错排公式:将n个错排数记为f[n]。将n中的第1个排错，假设放在第k个位置，就有n-1种放法。那么第k个可以放在第1个位置，剩下的还有n-2个进行错排，为f[n-2]；若第k个不放在第1个位置，则还有n-1个需要错排，为f[n-1]。因此得到错排数公式:f[n]=(n-1)*(f[n-1]+f[n-2])，其中f[0]=0.f[1]=0,f[2]=1。

  for(i=3; i<=25; i++)
        f[i]=(i-1)*(f[i-1]+f[i-2]);

本题中"女生们只要求他答对一半或以上就算过关"，因此就应该错排0个，1个，2个一直到n/2个，然后与排列数相乘再累加即可。注意这里应该选择的是组合数公式，而不是排列数公式。下面见代码，若还不理解可以回复~~

#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
using namespace std;
__int64 C_n_m(int n,int m)
{
    __int64 i,up,down;//分子，分母
    up=down=1;
    for(i=n;i>=n-m+1;i--)
        up*=i;
    for(i=m;i>=1;i--)
        down*=i;
    return up/down;
}
int main()
{
    int n;
    int i;
    __int64 f[30];
    f[0]=0;
    f[1]=0;
    f[2]=1;
    __int64 sum;
    for(i=3; i<=25; i++)
        f[i]=(i-1)*(f[i-1]+f[i-2]);
    while(~scanf("%d",&n))
    {
        sum=0;
        if(n==0)
            break;
        else
        {
            for(i=0; i<=n/2; i++)
                sum+=f[i]*C_n_m(n,i);
        }
        printf("%lld\n",sum+1);//当全部答对时f[0]=1，因此要加1.
    }
}<span style="font-size: 17px;">
</span>