作者:手浪用户2602925023 | 来源:互联网 | 2023-05-17 21:20
【数论】错排问题错排的定义:n个有序的元素应有n!个不同的排列,如若一个排列使得所有的元素不在原来的位置上,则称这个排列为错排>>>>分析我们来求一下递推式ヾ
【数论】错排问题
错排的定义:n个有序的元素应有 n ! 个不同的排列,如若一个排列使得所有的元素不在原来的位置上,则称这个排列为错排
>>>>分析
我们来求一下递推式ヾ(o・ω・)ノ
本蒟蒻在此引用CSDN上@zsheng_大佬的分析
当n个编号元素放在n个位置,元素编号与位置编号各不相同的方法数用f(n)表示,那么f(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数
第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;
第二步,放编号为k的元素,这时有2种情况:(k
(1) 把它放在位置n上,那么,对于剩下的n-1的元素,由于第k各元素放在位置n,剩下的n-2个元素就有f(n-2)种方法;
(2) 第k个元素不把它放在位置n,这时,对于这n-1个数就有f(n-1)种方法。
递推式
f[i]=(i-1)*f[i-2]+(i-1)*f[i-1]
初值:f[1]=0 f[2]=1
>>>>例题
【题目】
Mr. Hu 需要给机房的 n 位同学重新安排位置,为了使换位的效果好,需要保证每位同学在排位前和排位后所在的位置都不同。
Mr. Hu 想知道有多少种可能的排位方法。因为排位数可能很大,所以你只需要输出它模 109 + 7 的结果。
【输入格式】
输入文件中只有 1 个数 n,表示学生人数。
【输出格式】
输出可能的排位数取模后的结果。
【输入样例】
3
【输出样例】
2
>>>>代码
#include
#define ll long long
#define maxn 1000005
using namespace std;
const ll mod=1e9+7;
ll n,f[maxn];
int main()
{
// freopen("derange.in","r",stdin);
// freopen("derange.out","w",stdout);
scanf("%I64d",&n);
f[1]=0; f[2]=1;
for(ll i=3;i<=n;i++)
f[i]=(f[i-1]*(i-1)%mod+f[i-2]*(i-1)%mod)%mod;
printf("%I64d",f[n]);
return 0;
}
完结撒花✿✿ヽ(°▽°)ノ✿
题目来源:开学后的第二次周考