「题解」「GXOI&GZOI2019」逼死强迫症 obs

GXOI&GZOI2019 Day2 T1。

数据应该可以加强到 \(n\leq 10^{500000}\)。

题目链接: GXOI&GZOI2019 Day2 T1、Luogu P5303LibreOJ 3086

题目

题目描述

ITX351 要铺一条 \(2\times N\) 的路,为此他购买了 \(N\) 块 \(2\times 1\) 的方砖。可是其中一块砖在运送的过程中从中间裂开了,变成了两块 \(1\times 1\) 的砖块!
ITX351 由此产生了一个邪恶的想法:他想要在这条路上故意把两块 \(1\times 1\) 的砖块分开铺,不让两块砖有相邻的边,其他砖块可以随意铺,直到整条路铺满。这样一定可以逼死自身强迫症 sea5!

也许下面的剧情你已经猜到了——他为此兴奋不已,以至于无法敲键盘。于是,他请你帮忙计算一下,有多少种方案可以让自己的阴谋得逞。

数据范围

所有测试数据的范围和特点如下表所示:

测试点编号N 的规模T 的规模
1 N \le 10 T \le 10
2
3 N \le 10^5 T \le 50
4
5
6 N \le 2 \times 10^9
7
8
9 T \le 500
10

时空限制

题解

本题有多种解法。

解法 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\),读入时取模即可。