【每日一题】8月13日题目精讲

题号 NC19833
名称 地斗主
来源 牛客OI周赛3-提高组
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

先考虑直接递推能不能推：
如果前n-1行填满，第n行：两个1*2的竖着放，1种方法；
如果前n-2行填满（但是前n-1行没满）：横着两个，竖着两个有3种方法，横着四个有1种方法，一共4种；
如果n-3行填满（前n-1，n-2行没满），有2种情况；
如果n-4行填满的话，有3种情况；
n-大于等于3的奇数行填满——2种；
n-大于等于4的偶数行填满——3种；

;
省略号里面的东西在f[n-2]中也有所以我们把f[n-2]写出来化简它： ;
以上两个式子相减： f[n] = f[n-1] + 5f[n-2] + f[n-3] - f[n-4]；
然后使用矩阵快速幂即可

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目9月1日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴