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

题目链接:?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);

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

__int64 A_n_m(int n,int m){__int64 i,up=1;for(i=n;i>=n-m+1;i–)up*=i;return up;}组合数的代码为:

__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;}递推错排公式:将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.}}

喜欢真实的人，要做真实的人，所以从来不会想要刻意模仿任何人。

相关文章：

你感兴趣的文章：

标签云：