这道题，首先看N的值能够取到1000，说明递归已经无法解决问题了，只能从递推入手，$N==1$时 有一种方案，$N==2$时，有3种方案；当$N==3$时，左边取两列，右边只有一种方案，左边将$2*2$ 的放上面或者下面有两种，为什么不在左边全部放1*1，因为会在之后发生重复；左边取一列，右边就是 N==2时候的情况；所以我们就能得到递推公式$F(i)=F(i-1)+2*F(i-2)$. 代码如下：

#include <bits/stdc++.h>
using namespace std;
int f[1005];
int main()
{
	f[1]=1,f[2]=3;
	int n;
	cin>>n;
	for(int i=3;i<=n;++i)
	f[i]=(f[i-1]+2*f[i-2])%12190116;//根据所推出的递推公式，计算出题目所给范围内的方案数 
	cout<<f[n]<<endl;
}