题解

思路推导

队列只由步兵和骑兵两种字符组成。为了决定下一名士兵能否加入，需要知道已经使用的两类人数、队尾士兵类型以及队尾连续段长度。

设状态记录使用了 $i$ 个步兵、$j$ 个骑兵，最后一类士兵及其连续长度。若追加同类士兵，连续长度必须未达到对应上限；若追加另一类士兵，新连续段长度变为一。所有转移都对 $10^8$ 取模。

做法

分别以单个步兵和单个骑兵初始化。依次枚举使用人数和末段状态，尝试加入步兵或骑兵。最终把恰好使用 $n_1,n_2$ 人的所有末段状态求和。

当总人数不超过 18 时，可以枚举所有二进制队列。特殊地，当 $k_1=1$ 时，任意两个步兵之间至少要有一个骑兵；把骑兵数分配到步兵前后及相邻步兵之间的 $n_1+1$ 个间隙，并限制每个间隙不超过 $k_2$，即可用有界组成 DP 计数。

正确性证明

任意非空队列都有唯一的“已用步兵数、已用骑兵数、末段类型、末段长度”描述。算法只在追加后连续段不超过对应限制时转移，所以生成的每条状态路径都是优雅队列。

反之，任意优雅队列从左到右读取时，每一步都满足相应转移条件，并形成唯一的状态路径。因此算法不重不漏地统计全部优雅队列。终点要求两类人数恰好用完，末段状态求和即为答案。

复杂度分析

时间复杂度为 $O(n_1n_2(k_1+k_2))$，空间复杂度为 $O(n_1n_2(k_1+k_2))$。