错排问题错排公式 Hdu 1465 + 2048 +2049 + 2068 + 4535

小鱼儿 2022-08-25 10:52 150阅读 0赞

也称 伯努利-欧拉装错信封问题

n错排公式：F\[n\]=(n-1)\*(F\[n-1\]+F\[n-2\])

证明：

1.当前n-1个错排时：将其任意一封信与n对调,共(n-1)\*F\[n-1\]

2.当前n-2个错排，1个不错排时,将不错排的那封信与n对调,共(n-1)\*F\[n-2\]

3.当前≤n-3个错排，≥2个不错排时,显然无解.

∴F\[n\]=(n-1)\*F\[n-1\]+(n-2)\*F\[n-2\]

通项公式 ![D\_n=n!M\_n=n!(\\frac\{1\}\{2!\}-\\frac\{1\}\{3!\}+...+(-1)^n\\frac\{1\}\{n!\}).][D_n_n_M_n_n_frac_1_2_-_frac_1_3_..._-1_n_frac_1_n_.]

更多介绍 参见wiki ： [ 错排问题 - 维基百科，自由的百科全书][_ -]

**Hdu 1465 不容易系列之一**

#include <cstdio>  
    
    __int64 D[25]={0,0,1};
    
    int main ()  
    {
    	int n;
    	for (int i=3;i<=20;i++)
    		D[i]=(i-1)*D[i-1]+D[i-2]*(i-1);  
    	while (~scanf("%d",&n))
    		printf("%I64d\n",D[n]);
    	return 0;
    }

**Hdu 2048 神、上帝以及老天爷**

题目分析：错排公式的简单应用，错排公式为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!\];

本题7项之后对数值的影响就很小了，所以不必计算

#include <cstdio>
    
    int main ()
    {
    	int T,n;
    	double ans[8]={0,0,50,33.33,37.50,36.67,36.81,36.79};
    	scanf("%d",&T);
    	while(T--)
    	{
    		scanf("%d",&n);
    		if (n>=7)
    			printf("36.79%%\n");
    		else
    			printf("%.2lf%%\n",ans[n]);
    	}
    	return 0;
    }

**Hdu 2049 不容易系列之(4)——考新郎**

ans=C(n,n-m)\*D(m) ，m为找错的个数

#include <cstdio>
    
    const int N=25;
    __int64 C[N][N];
    __int64 D[N]={0,0,1};
      
    void Init () 
    {
        int i,j;
        for (i=1;i<=20;i++)
        {
            C[i][0]=C[i][i]=1;  
            for (j=1;j<i;j++) 
                C[i][j]=(C[i-1][j-1]+C[i-1][j]);  
        }
        for (i=3;i<=20;i++)
            D[i]=(i-1)*(D[i-1]+D[i-2]);
    }
    
    int main ()
    {
        int n,m,T;
        Init ();
        scanf("%d",&T);
        while (T--)
        {
            scanf("%d%d",&n,&m);
            printf("%I64d\n",C[n][n-m]*D[m]);
        }        
        return 0;
    }

**Hdu 2068 RPG的错排**

不可能只找对n-1组……

#include <cstdio>
    
    const int N=30;
    __int64 C[N][N];
    __int64 D[N]={0,0,1};
      
    void Init () 
    {
    	int i,j;
    	for (i=1;i<=25;i++)
    	{
    		C[i][0]=C[i][i]=1;  
    		for (j=1;j<i;j++) 
    			C[i][j]=(C[i-1][j-1]+C[i-1][j]);  
    	}
    	for (i=3;i<=25;i++)
            D[i]=(i-1)*(D[i-1]+D[i-2]);
    }
    
    int main ()
    {
    	int n;
    	Init ();
    	while (scanf("%d",&n),n)
    	{
    		int m=n-n/2;  //正确的个数
    		__int64 ans=0,temp;
    		for (int i=m;i<=n;i++)  
    			if (i!=n-1)  //不可能只找对n-1组……
    			{
    				temp=1;
    				if (n-i==0)  
    					temp=1;
    				else
    					temp=C[n][i]*D[n-i];  
    				ans+=temp;  
    			}
    			printf("%I64d\n",ans);
    	}		
    	return 0;
    }

**Hdu 4535 吉哥系列故事——礼尚往来**

#include <cstdio>
    
    const int mod = 1000000007;
    __int64 D[200] = {0,0,1};
    
    int main ()
    {
    	int T,n;
    	for (__int64 i=3;i<=100;i++)
    		D[i] = ((D[i-1]+D[i-2])%mod)*(i-1)%mod;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%d",&n);
    		printf("%I64d\n",D[n]);
    	}
    	return 0;
    }

[D_n_n_M_n_n_frac_1_2_-_frac_1_3_..._-1_n_frac_1_n_.]: /images/20220824/ad7281b4f3e940e88cf8451425dce0ec.png
[_ -]: http://zh.wikipedia.org/wiki/%E9%94%99%E6%8E%92%E9%97%AE%E9%A2%98