错排问题 && 洛谷 P1595 信封问题

传送门

一道裸的错排问题

错排问题

百度百科上这样说

就是对于一个排列，每一个数都不在正确的位置上的方案数。n 个元素的错排数记为 D(n)。

公式

D(n)=(n−1)∗(D(n−2)+D(n−1))

推出公式（感性）

对于第n个数，放在k位置上。

而第k个数有两种情况：

当第k个数放到n位置时，相当于把k和n交换了位置，对剩下的n-2个数没有任何影响，所以方案数为D(n-2)。
当第k个数不放到n位置时，相当于k由原来的不能放在k位置变成了不能放在n位置，对k和剩下的n-2个数即这n-1个数都没有影响，所以方案数为D(n-1)。

所以对于每个k，都有D(n-1)+D(n-2)种排法。而k有n-1种选择，所以要乘上n-1，最终得出公式D(n)=(n-1)*(D(n-1)+D(n-2))。

其中，D(1)初始化为0，D(2)初始化为1。

AC代码

 #include<iostream>

 using namespace std;

 long long ans[];

 int main()

 {

     int n;

     cin>>n;

     ans[]=;

     ans[]=;

     for(int i=;i<=n;i++) ans[i]=(i-)*(ans[i-]+ans[i-]);

     cout<<ans[n];

     return ;

 }

巴特西

错排问题 && 洛谷 P1595 信封问题

传送门

错排问题

公式

推出公式（感性）

AC代码

最新文章

热门文章