题解：P16811 [蓝桥杯 2026 国 Python A] 课程值班

· · 题解

意思就是每个连续段长度必须恰好为 2，整个串形如 0^{a_0}110^{a_1}110^{a_2}\cdots0^{a_{k-1}}110^{a_k}，其中 a_0,a_k\ge0，其余均 >0。将内部的 a_i 减去 1，剩下的总和为 n-3k+1，方案数为 \dbinom{(n-3k+1)+(k+1)-1}{(k+1)-1}=\dbinom{n-2k+1}{k}，当 n<3k-1 时方案数为 0。

设 F=\displaystyle{\sum_{k=1}^{+\infty}\binom{n-2k+1}{k}x^k}，令 L=\dfrac K2，所求即为 [x^L]F^m，直接多项式快速幂是 \mathcal O(K^2\log m) 的，用 NTT 可以做到 \mathcal O(K\log K\log m)，但数据范围比较小，考虑一些比较纯良的做法。

设 G=x^{-1}F=\displaystyle{\sum_{k=0}^{+\infty}\binom{n-2k-1}{k+1}x^k}，答案等于 [x^{L-m}]G^m，考虑递推 H=G^m 的系数，有 H'=mG'G^{m-1}，即 GH'=mG'H，比较 x^{k-1} 项的系数，有：

\sum_{i=0}^kih_i\cdot g_{k-i}=m\sum_{i=0}^{k-1}h_i\cdot(k-i)g_{k-i}\\ h_k=\dfrac{1}{kg_0}\sum_{i=0}^{k-1}(m(k-i)-i)h_ig_{k-i}

边界为 h_0=g_0^m，直接 \mathcal O(K^2) 递推即可，跑得飞快。

还有个小问题，当 n\equiv1\pmod{998244353} 时 g_0 会变成 0，往后找到第一个非 0 位置做即可。