Description：

用 $1\times2$ 的矩形和面积为 $3$ 的 $L$ 形去覆盖一个 $2\times N$ 的矩形，求方案数对 $10^4+7$ 取模后的结果。

$1\leqslant n\leqslant10^{100000}$

Solution：

设 $f[i][0/1]$ 为第 $i$ 列填满 $/$ 空一格的方案数，转移为: $$ f[i][0]=f[i-1][0]+f[i-2][0]+f[i-1][1] $$

$$ f[i][1]=f[i-1][1]+f[i-1][0]\times 2 $$

把第二个式子代入第一个，得： $$ f[i][0]=f[i-1][0]+f[i-2][0]+f[i-2][1]+f[i-2][0]\times 2 $$ 然后再把第一个式子的 $i-1$ 代入，得： $$ f[i][0]=f[i-3][0]+f[i-2][0]\times 2 $$ 反正最后要求的是 $f[n][0]$ ，可以用这种方法消去 $f[x][1]$ ，然后就可以矩阵快速幂了既然是高精那就用十进制矩阵快速幂可以一位一位处理。

还有一个做法是找循环节，发现是模数 $-1$ ，然后就很好做了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 10007

int n;

int f[MOD] = {1,1,2};

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = ((res << 1) + (res << 3) + c - '0') % (MOD - 1);

		c = getchar();

	}

	return res;

}

int main()

{

	n = read();

	for(int i = 3;i <= n;++i)

	{

		f[i] = (f[i - 1] * 2 + f[i - 3]) % MOD;

	}

	cout << f[n] << endl;

	return 0;

}