答题卡 题解
答题卡
https://ac.nowcoder.com/acm/contest/5389/C
考点:dp+思维
刚开始写的时候读不懂题意，不太明白如何下手，看了样例的图片后有了一些灵感，发现好像对称，索性找了一下规律。
发现我们可以把这个问题分为两种情况，第一种就是选左上角的格子，这样的话第一行第一列都不能涂，就是有dp[n-1]种；
如果不选左上角的格子，第一行还可以选n-1个格子，必须一次选两个对称的，这样就剩了dp[i-2]种可以选；
递推式为dp[i] = dp[i-1]+(i-1)*dp[i-2];
import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
public static void main(String args[])throws IOException
{
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
int n = (int)in.nval;
long dp[] = new long[1000000];
dp[1] = 1;
dp[2] = 2;
dp[3] =4 ;
dp[4] = 10;
long mod = 1000000007;
for(int i=5;i<=n;i++)
dp[i] = (dp[i-1]+(i-1)*dp[i-2])%mod;
out.println(dp[n]%mod);
out.flush();
}
} 
