test

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

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

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

①若 为奇数

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

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

②若 为偶数

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

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

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