题意：若
序列的任意一个长为
的连续子串中都有 个 或 个 ，则称为好序列。求长为 的好序列数目。
答案对 取模，，，时限 。
- 前置知识： 为
阶方阵，则矩阵列
存在不超过 阶的线性递推式。
考虑状态压缩 DP，记
表示长度为 ，末尾 位状态为
的方案数。转移时枚举下一位填什么即可。可以矩阵快速幂加速，但无法通过。
最差情况下，DP 中 的可能取值有
种，答案对应一个
阶矩阵的幂序列，故答案的最短递推式长度不超过 。
用 DP 求出 较小时的答案，BM
求最短递推式，然后求解线性递推。复杂度 。