HRBUSTOJ 2372 - 小L的问题

Author Avatar
Jimmy Zhang Mar 27, 2018
  • Read this article on other devices

题面

对于一个宽度为 22 长度为 nn 的棋盘,用 1×21 \times 2 大小的矩形骨牌和 33 格大小的 LL 型骨牌去填充棋牌并使得棋盘被完全覆盖。问方案的个数(对 109+710^9 + 7 取模)?

数据范围

1n10181 \le n \le 10^{18}

题目链接

分析

脚趾头想想都知道多半是动态规划。

我们会很自然的想到,记 dp[i]dp[i] 为完全覆盖长度为 ii 的棋盘所存在的方案数,并思考 dp[i]dp[i] 如何由之前的状态转移过来。

但是直接这样想是想不出来的(逃

我们来看看 i=4i = 4 时存在的下面这种情况:

一个神奇的情况

显然,这个情况是无法从之前的任何一个合法状态转移过来的。那么显然,这意味着我们光记录合法状态是不够的。

哼,既然光记录合法状态不够,那我就把所有状态都记录下来……

我们不难发现,对于每一列事实上都只有 44 种状态:

每列的四种状态

那么我们不妨用 dp[i][s]dp[i][s] 来表示第 ii 列之前均满,第 ii 列状态为 ss,且第 ii 列之后均空时的方案个数。

我们可以以此来思考一下每一个 dp[i][s]dp[i][s] 可以如何从 dp[i1][t]dp[i - 1][t] 转移而来:

状态转移

由上图,我们可以很直观地发现:

dp[i][0]dp[i][0] 可以在 dp[i1][3]dp[i - 1][3] 的基础上什么都不做得来;

dp[i][1]dp[i][1] 可以在 dp[i1][0]dp[i - 1][0] 的基础上加一个 LL 型骨牌,或在 dp[i1][2]dp[i - 1][2] 的基础上横着加一个 1×21 \times 2 骨牌得来;

dp[i][2]dp[i][2] 可以在 dp[i1][0]dp[i - 1][0] 的基础上加一个 LL 型骨牌,或在 dp[i1][1]dp[i - 1][1] 的基础上横着加一个 1×21 \times 2 骨牌得来;

dp[i][3]dp[i][3] 可以在 dp[i1][0]dp[i - 1][0] 的基础上横着加两个 1×21 \times 2 型骨牌,或在 dp[i1][1]dp[i - 1][1] 的基础上加一个 LL 型骨牌, 或在 dp[i1][2]dp[i - 1][2] 的基础上加一个 LL 型骨牌,或在 dp[i1][3]dp[i - 1][3] 的基础上竖着加一个 1×21 \times 2 型骨牌得来;

即得出:

{dp[i][0]=dp[i1][3]dp[i][1]=dp[i1][0]+dp[i1][2]dp[i][2]=dp[i1][0]+dp[i1][1]dp[i][3]=dp[i1][0]+dp[i1][1]+dp[i1][2]+dp[i1][3]\begin{cases}
dp[i][0] = dp[i - 1][3] \
dp[i][1] = dp[i - 1][0] + dp[i - 1][2] \
dp[i][2] = dp[i - 1][0] + dp[i - 1][1] \
dp[i][3] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] \
\end{cases}

而我们最后要求的答案,也就是 dp[n][3]dp[n][3]

ans[n]=dp[n][3]ans[n] = dp[n][3]

最后,我们也不难找出边界情况,也就是:

{dp[1][0]=1dp[1][1]=0dp[1][2]=0dp[1][3]=1\begin{cases}
dp[1][0] = 1 \
dp[1][1] = 0 \
dp[1][2] = 0 \
dp[1][3] = 1 \
\end{cases}

当然,你也可以简单地记作:

dp[0][3]=1dp[0][3] = 1


在此基础上,我们还可以考虑对原转移方程进行化简:

ans[i]=dp[i][3]=dp[i1][0]+dp[i1][1]+dp[i1][2]+dp[i1][3]=dp[i2][3]+dp[i2][0]+dp[i2][2]+dp[i2][0]+dp[i2][1]+ans[i1]=(dp[i2][0]+dp[i2][1]+dp[i2][2]+dp[i2][3])+ans[i1]+dp[i2][0]=2ans[i1]+dp[i2][0]=2ans[i1]+dp[i3][3]=2ans[i1]+ans[i3]\begin{aligned}
ans[i] &= dp[i][3] \
&= dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] \
&= dp[i - 2][3] + dp[i - 2][0] + dp[i -2][2] +dp[i - 2][0] + dp[i - 2][1] + ans[i - 1] \
&= (dp[i - 2][0] + dp[i - 2][1] + dp[i - 2][2] + dp[i - 2][3]) + ans[i - 1] + dp[i - 2][0] \
&= 2 \cdot ans[i - 1] + dp[i - 2][0] \
&= 2 \cdot ans[i - 1] + dp[i - 3][3] \
&= 2 \cdot ans[i - 1] + ans[i - 3] \
\end{aligned}

于是我们由此得到了:

ans[i]=2ans[i1]+ans[i3]ans[i] = 2 \cdot ans[i - 1] + ans[i - 3]

实现

看看题目的数据范围就知道可能要用到矩阵快速幂。这里就略去了。

HRBUST OJ 貌似关闭注册了,懒得写了(逃

反正这道题还是思维最重要,代码写起来也很简单的。

%%%

呜呜呜怎么大家都会打表找规律啊QAQ 我太辣鸡了。

感谢以下巨佬在本辣鸡弄懂该题过程种给予的帮助:

  • zzy
  • Hanano
  • BinGoo0o0o
  • DeaphetS
  • jackyan

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/03/27/hrbustoj-2372/