题目大意

有 I 形和 L 形两种砖头，分别能覆盖 2 个单元和 3 个单元。求 $2 \times n$ 的墙有多少不重复的覆盖方式，结果对 $10^4$ 取模。

分析

其中 I 形砖块仅有横放和竖放两种。关键在于 L 形，两个 L 形之间可以用 I 形填充，这让情况变得复杂起来。

对于 $F_n$ 的递推，我们可以想到

  • 在 $F_{n-1}$ 后放一个 I 形砖块。
  • 在 $F_{n-2}$ 后放两个横着的 I 形砖块。
  • 对于更前面的递推，较为复杂。
    • 两个 L 形砖块对齐，上下翻转也可以，即 $2 F_{n-3}$。
    • 两个 L 形砖块可以对顶放，空缺恰用一个 I 填充，即 $2 F_{n-4}$。
    • 类似 $2F_{n-3}$，中间可以再插入两个 I 形，即 $2 F_{n-5}$。
    • ……
    • 直到 I 形和 L 形砖块恰好铺满墙壁，即 $2F_{0}$。

容易得到我们的递推式

$$ F_n = F_{n-1} + F_{n-2} + 2 \sum_{i=0}^{n-3} F_i $$

利用错位相减法，不难化简得到

$$ F_n = 2 F_{n-1} + F_{n-3} $$

于是代码有

int dp[1000000];

int main() {
	int n = rr();
	dp[1] = 1, dp[2] = 2, dp[3] = 5;
	for (ll i = 4; i <= n; i++)
		dp[i] = (dp[i - 1] * 2 + dp[i - 3]) % 10000;
	printf("%d\n", dp[n]);
	return 0;
}