首页 > 代码库 > wikioi 1697 ⑨要写信

wikioi 1697 ⑨要写信

2024-07-07 22:26:33   222人阅读

把n个元素的错排数记为Dn，显然D1=0，D2=1。当n≥3时，设不错排时i位置的元素为a[i]，不妨设最后一个数a[n]排在了第k位，其中k≠n，也就是1≤k≤n-1。那么我们现在考虑第n位的情况。

  • 当a[k]排在第n位时，a[n]与a[k]的位置均已确定，除了a[n]和a[k]以外还有n-2个数，其错排数为Dn-2。
  • 当a[k]不排在第n位时，只有a[n]的位置确定（占据了k位置），那么这时的包括a[k]在内的剩下n-1个数的每一种错排，都等价于只有n-1个数时的错排(因为已经假设a[k]不能排在第n位，所以这时的第n位可看作a[k]的“本位”，即是错排时a[k]不能占据的“第k位”）。其错排数为Dn-1。

    所以当n排在第k位时共有Dn-2+Dn-1种错排方法，又k位置有从1到n-1共n-1种取法，我们可以得到：
    Dn=(n-1)(Dn-1+Dn-2)

 

这里注意，我的代码没加大数运算算法，不然会溢出的（这一块后面再补）

 1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 #include <ostream>
 8 #include <vector>
 9 #include <list>
10 using namespace std;
11 
12 int main()
13 {
14     int N;
15     cin>>N;
16     vector<int> dp;
17     dp.push_back(0);
18     dp.push_back(0);
19     dp.push_back(1);
20     int i;
21     for(i = 3 ; i <= N ; ++i)
22     {
23         dp.push_back((i-1)*(dp[i-1]+dp[i-2]));
24     }
25     cout<<dp[N]<<endl;
26     return 0;
27 }

 


联系
我们