今天因为不会 伯努利-欧拉装错信封问题 被附近的大佬狠狠地嘲讽了一下,去学习了一下发现,这确实是个经典而有趣的问题,今天就让我们来分享一下这个问题吧!

什么是伯努利-欧拉装错信封问题

伯努利-欧拉装错信封问题 又称 错位重排问题,具体来说,就是——

我们有编号是1、2、…、n的n封信,装入编号为1、2、…、n的n个信封,要求每封信和信封的编号不同,即1不能装进1,2不能装进2,3不能装进3……问有多少种装法?

最开始看到这个问题时,第一反应就是通过组合数学进行计算。当然很多人第一反应都是,我们对于每一个i,前i-1个错位重排的可能排列一共有 a 种,那我对于每一种,,貌似都可以找除了最后一个位置进行插入(即除了红色箭头外的其他绿色箭头),又由于共有i-1个绿色箭头,所以共有i-1个插入位置,这样我插入的第i个数也满足错位重排了,如下:

1.png

这样貌似算出来对于任意 i ,设F[i]为1-i的错位重排的数量,都有 F[i]=F[i-1]*(i-1)。

于是你很开心认为可以AC了,然后你就WA了,那么问题出现在哪里呢?其实,你上面推导的这一整个公式都是错的!

错误分析

我们来分析一下上面推导的公式为什么是错误的。我们在上面先对于处理第i封信放在哪里时,都会在每一个i-1的错位排列的基础上,在每一种i-1的错位排列的情况上把第i封信放在初最末尾外的其他位置。对这样对于第i封信来说,是已经满足错位排列了,但是你有没有想过,当你把一封信插在原来的[x,y]两封信之后,原来排在[y,i-1]的信都集体后移了一位,那移动后那段序列还符合错位排列吗?

不一定了,比如,我们要求4的错位排列数量,我们就先搞出一个3的错位排列:

2.png

然后我们准备把4插进来:

3.png

但按照原来的策略,我们完全可以把4插到最前面,这样4就满足错位排列了,但是2,3,1的后移导致了2,3都不符合错位排列了,这样就和我们的题目相违背了:

4.png

那我们不妨换一个思路想想。

正确的解法

我们设,设f[i]为i个数错位排序 (任意1<=i<=n a[i]!=i)通过常理我们知道:f[0]=1,f[1]=0;那么有

f[i]=(f[i-1]+f[i-2])*(i-1) (i>=2)

对这就是我们的结论了,但是这是为什么吗?不急我现在就告诉你证明的方法:

对于插入第i个元素,只有两种情况:
情况1:插入第i个元素时,前i-1个已经错位排好,则选择其中任意一个与第i个互换一定满足要求,选择方法共i-1种,前i-1位错排f[i-1]种,记f[i-1]*(i-1),如下图:

5.png

情况2:插入第i个元素时,前i-1个中恰有一个元素a[j]使得a[j]=j,即恰好只有一个元素不满足错位排列,其他i-2个错位排好,则将i与j交换,j在i-2位中的插入共i-1种,前i-2位错排f[i-2]种,记f[i-2]*(i-1),如下图:

6.png

以上两种情况求和可得:

f[i]=(f[i-1]+f[i-2])*(i-1) (i>=2)

*来个通项公式

QwQ.png

酱紫就得到我们的通项公式了!

*进一步讨论

QAQ.png

经典例题

[luogu p3182]即[HAOI2016]放棋子
题目描述
给你一个N*N的矩阵,每行有一个障碍,数据保证任意两个障碍不在同一行,任意两个障碍不在同一列,要求你在这个矩阵上放N枚棋子(障碍的位置不能放棋子),要求你放N个棋子也满足每行只有一枚棋子,每列只有一枚棋子的限制,求有多少种方案。

输入输出格式
输入格式:
第一行一个N,接下来一个N*N的矩阵。N<=200,0表示没有障碍,1表示有障碍,输入格式参考样例

输出格式:
一个整数,即合法的方案数。

输入输出样例
输入样例#1:
2
0 1
1 0
输出样例#1:
1

这一眼看过去就是伯努利-欧拉装错信封问题的裸题,由于开始时给的棋子在哪一行哪一列都不重要,因为求出来的答案都是一样的,所以我们只要把棋子i的、挪到第i行第i列就好了,剩下的问题就变成了,你有n个棋子,每列放一个,第i个棋子不能放在第i行,有多少种情况。这不是就是伯努利-欧拉装错信封问题吗?

注意n比较大要开高精度!!!附上模板:

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int a[1100000],b[1100000],c[1100000];
int i,j,k,m,n,o,p,q,js,jl,jk,lena,lenb,lenc;
int my_max(int x,int y)
{
    if(x>y)return(x);
    else return(y);
}

int caozuo(int x)
{
    lenc=lenb;
    for(int i=1;i<=lenb;i++)
    {
        c[i]=a[i]+b[i];
        c[i]=c[i]+c[i-1]/10;
        c[i-1]=c[i-1]%10;
    }
    if(c[lenc]>=10)
    {
        c[lenc]-=10;
        c[++lenc]=1;
    }

    for(int i=1;i<=lenc;i++)
    {
        c[i]=c[i]*(x-1);
        c[i]=c[i]+c[i-1]/10;
        c[i-1]=c[i-1]%10;
    }

    while(c[lenc]>=10)
    {
        c[++lenc]=c[lenc-1]/10;;
        c[lenc-1]=c[lenc-1]%10;
    }

    lena=lenb;lenb=lenc;
    while(c[lenc]==0)lenc--;
    for(int i=1;i<=lena;i++)a[i]=b[i];
    for(int i=1;i<=lenb;i++)b[i]=c[i];
} 
int main()
{
    scanf("%d",&n);
    a[1]=0;b[1]=1;c[1]=1;
    lena=1;lenb=1;lenc=1;
    if(n==1)
    {
        printf("0");
        exit (0);
    }

    if(n==2)
    {
        printf("1");
        exit (0);
    }

    for(int i=3;i<=n;i++)
    {
        caozuo(i); 
    }
    for(int i=lenc;i>=1;i--)printf("%d",c[i]);
    return 0;
}

结语

在这篇BLOG中,我们学习了非常经典的伯努利-欧拉装错信封问题,注释*的框体均参考文献-武汉大学刘学智的论文《关于装错信封的讨论》。希望你能切实掌握这种算法,不要像我一样被大佬们嘲笑。希望你喜欢这篇BLOG!

Last modification:February 22nd, 2019 at 11:04 pm
If you think my article is useful to you, please feel free to appreciate