答题卡

题意：

求n * n的网格图横竖对称的填法

思路：

假设是个n * n的网格图，如果第一行放在第一列那就剩下的（n-1） * （n-1）化简问题 ， 如果第一行放在第二列 ， 那第二行的位置也就固定了，剩下（n-2） * （n-2），同理第三第四。。。。，除去第一行有 n - 1 行
所以可以得出dp[ i ] = dp[ i - 1 ] + （i-1）*dp[ i - 2 ]

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[100005];
int main(){
    dp[0] = dp[1] = 1;dp[2] = 2;
    ll n;
    cin>>n;
    for(int i = 3 ; i <= n ;++i){
        dp[i] = (dp[i-1] + (i-1)*dp[i-2])%mod;
    }
    cout<<dp[n]<<endl;
}