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\),读入时取模即可。
近期评论