题目链接
题解:
错排公式:d[n] = (n-1)(d[n-1] + d[n-2]);
最近在看组合数学,还没有看到这一部分,只能先搬过来用了。
#include <stdio.h> #include <cstring> #include <cmath> #include <iostream> #include <queue> #include <map> #include <list> #include <utility> #include <set> #include <algorithm> #include <deque> #include <iomanip> #include <vector> #define mem(arr, num) memset(arr, 0, sizeof(arr)) #define _for(i, a, b) for (int i = a; i <= b; i++) #define __for(i, a, b) for (int i = a; i >= b; i--) #define IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; typedef long long ll; typedef vector<int> vi; const ll INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const int N = 20 + 5; ll d[N]; int main() { d[2] = 1; _for(i, 3, N-1) d[i] = (i-1) *(d[i-1] + d[i-2]); int n; while(cin >> n) cout << d[n] << endl; return 0; }