test

知识点:动态规划、前缀和

题目大意:将 拆成一些数之和,要求不能有连续的两个奇数或连续的两个偶数。问有多少种方案数。对 取模。

思路:我们先考虑一般的递推形式。设 代表最后一步为偶数的方案数, 代表最后一步为奇数的方案数。那么我们可以得到如下的递推式:

①若 为奇数

代表最后一步加了个偶数形成了一个奇数,它的前一步必须是奇数,并且前一步的结尾必须是奇数结尾。

代表最后一步加了个奇数形成了一个奇数,它的前一步必须是偶数,并且前一步的结尾必须是偶数结尾。

②若 为偶数

代表最后一步加了个偶数形成了一个偶数,它的前一步必须是偶数,并且前一步的结尾必须是奇数结尾。

代表最后一步加了个奇数形成了一个偶数,它的前一步必须是奇数,并且前一步的结尾必须是偶数结尾。

这样得到的复杂度为 ,解决本题还是不够的。不过我们可以观察到,所有的偶数和奇数部分可以用前缀和加速达到 来解决。

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务