学步园

题目分析：错排公式的简单应用，错排公式为f(n) = n![1-1/1!+1/2!-1/3!+……+(-1)^n*1/n!]要求的概率为P=f(n)/n!;

P=[1-1/1!+1/2!-1/3!+……+(-1)^n*1/n!];

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int n,C;
	scanf("%d",&C);
	while(C--)
	{
		scanf("%d",&n);
		double ans=0;
		int arr[11]={1,1,2,6,24,120,720,5040,40320,362880,36288000};
		if(n<=10)
		{
			for(int i=2;i<=n;i++)
				if(i%2==0)
				    ans+=1.0/arr[i];
				else
					ans-=1.0/arr[i];
               
		}
		else
		{
			for(int i=2;i<=10;i++)
				if(i%2==0)
				    ans+=1.0/arr[i];
				else
					ans-=1.0/arr[i];
               
		}
		printf("%.2lf%%\n",ans*100);
	}
	system("pause");
	return 0;
}

hdu 2049 考新郎

分析后可知：ans=C(n,n-m)*f(m)，f(m)为m的错排

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	__int64 arr[25];
	arr[1]=0;
	arr[2]=1;
	for(int i=3;i<=20;i++)
		arr[i]=(i-1)*(arr[i-1]+arr[i-2]);
	/*for(int i=0;i<=20;i++)
		printf("%I64d\n",arr[i]);*/

	int C;
	scanf("%d",&C);
	while(C--)
	{
		int n,m;
		scanf("%d %d",&n,&m);
		m=n-m;//m对找对了
        __int64 ans=1;
		for(int i=1;i<=m;i++)
			ans=ans*(n-i+1)/i;
	    
		ans=ans*arr[n-m];
		printf("%I64d\n",ans);
	}
	system("pause");
	return 0;
}

hdu 2068  RPG的错排，给出了n，求猜对一半以上，所以猜对的有 n-n/2,  ,  ,n;还有不等于n-1

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	__int64 arr[25];
	arr[0]=0;
	arr[1]=0;
	arr[2]=1;
	for(int i=3;i<=20;i++)
		arr[i]=(i-1)*(arr[i-1]+arr[i-2]);
	while(1)
	{
		int n,m;
		scanf("%d",&n);
		if(n==0)
			break;

		m=(n-n/2);//m对找对了
        __int64 ans=0,temp;
		for(int k=m;k<=n;k++)
		{
			if(k!=n-1)
			{
			   temp=1;
		       for(int i=1;i<=k;i++)
			       temp=temp*(n-i+1)/i;
		       if(n-k==0)
				   temp=1;
			   else
		           temp=temp*arr[n-k];
              /* printf("%d***\n",temp);*/
			   ans+=temp;
			}
		}
		printf("%I64d\n",ans);
	}
	system("pause");
	return 0;
}