全错位重排
基本简介
一个人写了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位时,除了n和k以外还有n-2个数,其错排数为Dn-2。
· 当k不排在第n位时,那么将第n位重新考虑成一个新的“第k位”,这时的包括在内的剩下n-1个数的每一种错排,都等价于只有n-1个数时的错排(只是其中的第k位会换成第n位)。其错排数为Dn-1。
所以当n排在第k位时共有Dn-2+Dn-1种错排方法,又k有从1到n-1共n-1种取法,我们可以得到:
Dn=(n-1)(Dn-1+Dn-2)
得到递推的公式之后,我们再通过累加法可以推得全错位重排的通项公式为:
然后将其简化(供参考)可得Dn=[n!/e+0.5],其中e是自然常数,[]为向下取整。
对于该简化公式可以通过e的麦克劳林展开式(泰勒公式)推导出来:
+ 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