牛牛即将要参加考试，他学会了填答题卡。

可惜他竖着的答题卡填成了横着的 : (

好奇的他想知道对于 n 道题，每道题 n 个选项的答题卡 ( n * n 的矩阵 )，满足横答题卡和竖答题卡图形一致的方案数有多少种。

注：每道题只能选择一个选项，即 n * n 的矩阵中只能涂黑 n 个空。求横竖对称的方案数。

输入描述:

第一行给出 n。

输出描述:

输出方案数，答案对  取模

3

4

备注:

对于  的数据有 

对于  的数据有 

解题思路

比较明显的规律或者动态规划的题目，先从小开始慢慢推一下吧。
找到前4项是 1,2,4,10。你会发现第四项有点规律了。但是没有关系，我们有一个神奇的网站OEIS跳转里面第一个。
找到递推关系式：

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}


const int N = 1e5+7;
const int MOD = 1e9+7;
ll dp[N]={1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536};

int main(){
    int n=read();
    for(int i=15;i<=n;++i)
        dp[i]=(dp[i-1]+(i-1)*dp[i-2])%MOD;
    printf("%lld\n",dp[n]);
    return 0;
}

那么竟然有这个递推式子，我们返过去看看怎么推出它来。
给定一个n阶方阵，我们想第一行如果放在第一列上剩下的就是(n - 1) * (n - 1)的题目所求方案数，如果第一行不放在第一列一共有（n - 1）种方法，比如说返在第二列，那么对应第二行就唯一确定了只能放在第一列，除开这俩行，剩下（n - 2） * （n - 2）的题目所求方案数。
综上所述：dp[1] = 1; dp[2]=2
dp[i] = dp[i-1] + (i-1) * dp[i-2] (i>=3)
也是得到了我们的递推式。