全错位重排「建议收藏」

全错位重排「建议收藏」全错位重排基本简介一个人写了n封不同的信及相应的n个不同的信封,他把这n封信全都装错了信封,问都装错信封的装法有多少种? 解法:      将这n封信从1到n进行编号得到1、2、3……号码,同理将信封也从1到n进行编号,将n封信与信封错位的方法记作S。      1.当n=1时,由于只有1封信,所以无论如何都不会错位,所以此时S=0;      2.当n=2时,只能将1号信装进2号信封,2号…

全错位重排

基本简介

一个人写了n封不同的信及相应的n个不同的信封,他把这n封信全都装错了信封,问都装错信封的装法有多少种?

 

解法:

       将这n封信从1到n进行编号得到1、2、3……号码,同理将信封也从1到n进行编号,将n封信与信封错位的方法记作S。

       1.当n=1时,由于只有1封信,所以无论如何都不会错位,所以此时S=0;

       2.当n=2时,只能将1号信装进2号信封,2号信装进1号信封,因而S=1;

       3.当n=3时有(此处的编号为信的编号,所在位置为信封的编号):①3 1 2

                                                                                                                  ②2 3 1

         故此时S=2;

       4.同理可以推出S=9;

       ……

       当n较小时我们可以通过和上面一样枚举得到,,n=6时就已经是256了,枚举时一不小心错了一种就会翻车,所以当n比较大时枚举就行不通了,接下来就看下递推数列法:

显然D1=0,D2=1。当n>=3时,不妨设n排在了第k位,其中k≠n,也就是1<=k<=n-1。那么考虑第n位的情况。

·  k排在第n位时,除了nk以外还有n-2个数,其错排数为Dn-2

·  k不排在第n位时,那么将第n位重新考虑成一个新的k,这时的包括在内的剩下n-1个数的每一种错排,都等价于只有n-1个数时的错排(只是其中的第k位会换成第n位)。其错排数为Dn-1

所以当n排在第k位时共有Dn-2+Dn-1种错排方法,又k有从1n-1n-1种取法,我们可以得到:

Dn=(n-1)(Dn-1+Dn-2)

得到递推的公式之后,我们再通过累加法可以推得全错位重排的通项公式为:

Dn=n!*(1/0!-1/1!+1/2!-1/3!+……+(-1)^n/n!)

然后将其简化(供参考)可得Dn=[n!/e+0.5],其中e是自然常数,[]为向下取整。

对于该简化公式可以通过e的麦克劳林展开式(泰勒公式)推导出来:

e^x =1+x+x^2/2!+x^3/3!+……+x^n/n!
+ Rn(-1)

其中Rn(-1)是余项,等于(-1)^(n+1) * e^u / (n+1)!,且u(-1, 0).

所以,D(n) = n! *e^(-1) – (-1)^(n+1) * e^u / (n+1), u(-1, 0).

|n! Rn| =|(-1)^(n+1) * e^u / (n+1)| = e^u / (n+1) (1/[e(n+1)], 1/(n+1)),可知即使在n=1时,该余项(的绝对值)也小于1/2

 

这题还可以通过容斥定理推出:

正整数1,2, 3, ……, n的全排列有 n! 种,其中第k位是k的排列有 (n-1)! 种;当k分别取1, 2, 3, ……, n时,共有n*(n-1)!种排列是至少放对了一个的,由于所求的是错排的种数,所以应当减去这些排列;但是此时把同时有两个数不错排的排列多排除了一次,应补上;在补上时,把同时有三个数不错排的排列多补上了一次,应排除;……;继续这一过程,得到错排的排列种数为D(n) = n! – n!/1! + n!/2! – n!/3! + … + (-1^n*n!/n!= ∑(k=2~n) (-1)^k * n! / k!,

这与我们上面通过递推得到的形式相同!

这个通项公式我们还可以通过二项式反演、多项式模拟推出,大家如果感兴趣的话可以自行百度,我就不在此阐述了~

例题:

下面我们就来看一道全错位重排的题吧~(也是全错位重排的递归代码)

题目链接:https://www.nowcoder.net/acm/contest/78/G

题目描述:

  在家好冷!

又多冷呢?

大概是零下e度!

为什么是零下e度呢?

不知道,因为我编不下去了。

  求给定一个数n,求出最接近n!/e的整数

 

输入描述:

一行一个整数n1<=n<=10^8

 

输出描述:

一行一个整数,即题目描述中所求,由于这个数字可能很大,我们只需要知道mod998244353后的结果(出题人负责任地告诉你,这个数字是个质数)

 

示例1

输入

6

 

输出

265

 

示例2

输入

87

 

输出

158005593

 

示例3

输入

16777216

 

输出

16065816

 

解析:本题的n!/e就是错位重排的简化公式去掉余项,因而可以通过递推得到。我一开始是想靠打表过的,最后发现自己的空间一直比题目限制的大1K,看了别人的代码之后才发现并不需要打表,就在输入后面用for即可,emmmm

下面是我的代码:

#include <bits/stdc++.h>
using namespace std;

int n;

int main(){
    while(~scanf("%d",&n)){
        long long ans,a=0,b=1;
        if(n==1){
            printf("%lld\n",a);
        }
        else if(n==2){
            printf("%lld\n",b);
        }
        else{
            for(int i=3;i<=n;i++){
                ans=((i-1)*(a+b)%998244353)%998244353;
                a=b;
                b=ans;
            }
            printf("%lld\n",ans);
        }
    }
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/7279.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注