GXOI&GZOI2019 Day2 T1。
数据应该可以加强到 \(n\leq 10^{500000}\)。
题目链接： GXOI&GZOI2019 Day2 T1、Luogu P5303、LibreOJ 3086。
题目
题目描述
ITX351 要铺一条 \(2\times N\) 的路，为此他购买了 \(N\) 块 \(2\times 1\) 的方砖。可是其中一块砖在运送的过程中从中间裂开了，变成了两块 \(1\times 1\) 的砖块！
ITX351 由此产生了一个邪恶的想法：他想要在这条路上故意把两块 \(1\times 1\) 的砖块分开铺，不让两块砖有相邻的边，其他砖块可以随意铺，直到整条路铺满。这样一定可以逼死自身强迫症 sea5！
也许下面的剧情你已经猜到了——他为此兴奋不已，以至于无法敲键盘。于是，他请你帮忙计算一下，有多少种方案可以让自己的阴谋得逞。
数据范围
时空限制
题解
本题有多种解法。
解法 A（暴力）
别说这个你都不会。
解法 B（构造递推式）
设 \(g _ i\) 为 \(n=i\) 时的答案。
如果第 \(i\) 列不放 \(1\times 1\) 的小块，则对答案的贡献显然是 \(g _ {i-1}+g _ {i-2}\)。
如果第 \(i\) 列放小块，那么之前的每一列都可以放小块，且仅有一种方法。且该小块将前 \(i-2\) 列分成两部分，左部分的放置方案数显然为 \(f _ i\)，右部分唯一确定，根据乘法原理，对答案的贡献为 \(2\sum^{i-3} _ {j=0} f _ j\)，其中的 \(2\) 是右边小块的上下两种方式的贡献。
最后得出递推式
\[g _ n=g _ {n-1}+g _ {n-2}+2h _ {i-3}\]
其中 \(h _ i\) 是斐波那契数列的前缀和（下标从 \(0\) 开始）。
解法 C（矩阵）
其实就是解法 B 套了个矩阵。
解法 D（新递推式）
之前做法的推理过程中不难发现，如果两个小块的位置固定，则他们之间的摆放方案固定，不难得出答案为
\[
\begin{aligned}
\texttt{ans}&=2\sum^n _ {i=3}\sum^{n-i} _ {j=0}f _ jf _ {n-i-j}\\
&=2\sum^{n-3} _ {i=0}f _ i\sum^{n-i-3} _ {j=0}f _ j\\
&=2\sum^{n-3} _ {i=0}f _ i(f _ {n-i-1})\\
&=2-2f _ {n-1}+2\sum^{n-3} _ {i=0}f _ if _ {n-i-1}
\end{aligned}
\]
设 \(s _ n=\sum^n _ {i=0}f _ if _ {n-i}\) ，则有
\[s _ n=f _ n+s _ {n-1}+s _ {n-2}\]
用 \(f _ i,s _ i\) 可得出答案为
\[2(1+s _ {n-1}-2f _ {n-1}-f _ {n-2})\]
解法 E（生成函数）
\[
\begin{aligned}
\texttt{ans}&=2\sum^n _ {i=3}\sum^{n-i} _ {j=0}f _ jf _ {n-i-j}\\
&=2\sum^{n-3} _ {i=0}f _ i\sum^{n-i-3} _ {j=0}f _ j\\
&=2\sum^{n-3} _ {i=0}f _ i(f _ {n-i-1})\\
&=2-2f _ {n-1}+2\sum^{n-3} _ {i=0}f _ if _ {n-i-1}
\end{aligned}
\]
\[\texttt{ans}(x)=\frac{2x^3}{(1-x)(1-\frac{1+\sqrt{5}}{2}x)^2(1-\frac{1-\sqrt{5}}{2}x)^2}\]
经过一系列推导可得答案为
\[
\begin{aligned}
2&\\
&+\left(\frac{1+\sqrt{5}}{2}n-\frac{22\sqrt{5}}{50}-1\right)\left(\frac{1+\sqrt{5}}{2}\right)^n\\
&+\left(\frac{1-\sqrt{5}}{2}n-\frac{22\sqrt{5}}{50}-1\right)\left(\frac{1-\sqrt{5}}{2}\right)^n
\end{aligned}
\]
解法 F（神仙做法）
不难发现答案是斐波那契数列的递归树上各结点深度之和。
所以得出答案为
\[2+\frac{2(4n-9)f _ {n+1}+2(3n-5)f _ n}{5}\]
考虑到这里斐波那契数列循环节为 \(2\times 10^9+14\)，读入时取模即可。
近期评论