F - Fairy, the treacherous mailman

菜鸡复健

F. Fairy, the treacherous mailman
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Fairy is a very excentric mailman. Every now and then, he likes to change some correspondences that he is responsible for, swapping than to different addresses, as he enjoys the consequent turmoil. One day, Fairy was in his most inspired self and decided to swap all correspondences from their original addresses. No address should receive its intended correspondence. It will be Fairy’s ultimate masterpiece. Although he is keen to chaos, Fairy is also a very curious person, and he asked himself about how many ways he could swap the correspondences so none of the addresses receive the correct message. As he’s very lazy, he decided to ask your help to fulfill his objectives. You’ll receive an integer number N, that stands for the correspondences amount, to which you should generate another integer S that stands for the amount of ways he can swap the correspondences. Help Fairy in his mischievous plan, or he might change your correspondence as well.

Input
A unique integer N, (1≤N≤20) standing for the amount of correspondences.

Output
A unique integer S, representing the amount of ways Fairy can swap the correspondences. As the possibilities amount can be very big, the answer should be given as S mod 109+7.

Example
inputCopy
3
outputCopy
2

题意：input一个数字代表需要送的信的数量，output全部送错的可能性的数量（mod1e9+7）

思路：一个非常普通的数学签到题，有点dp的意思，dp[i]=(i-1)(dp[i-1]+dp[i-2];
假设现在是第i封信，第i封信可以放在（i-1）个可能性里面。
假设被放的那封信放在第i个位置上，剩下的信封可能性就是dp[i-2]，如果不可以放在第i个位置上，就相当于dp[i-1]的情况。主要是看题解的时候没能理解为什么是dp[i-1]。

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<list>
#include<math.h>
#include<vector>
#include<stack>
#include<string>
#include<set>
#include<map>
#include<numeric>
#include<stdio.h>
#include<functional>
#include<time.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5 + 10;
const ll mode = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double pi = 3.14159265358979323846264338327950;
template <class T> inline T min(T a, T b, T c) { return min(min(a, b), c); }
template <class T> inline T max(T a, T b, T c) { return max(max(a, b), c); }
template <class T> inline T min(T a, T b, T c, T d) { return min(min(a, b), min(c, d)); }
template <class T> inline T max(T a, T b, T c, T d) { return max(max(a, b), max(c, d)); }

ll ans[22] = { 0 };
int main()
{
	ll n;
	cin >> n;
	ans[0] = 0; ans[1] = 0;
	ans[2] = 1; ans[3] = 2;
	for (int i = 4; i <= 20; i++)
	{
		ans[i] = (i - 1)*((ans[i - 1] + ans[i - 2]) % mode) % mode;
	}
	cout << ans[n] << endl;

	return 0;
}