ABC258Ex Odd Steps 做题记录

给定 $N$、$S$ 和长度为 $N$ 的序列 $A$，找到满足以下条件的序列 $X$ 的个数对 $998244353$ 取模后的结果：

• $X$ 的每个元素都是正奇数
• $\sum X_i=S$
• 设 $Y_i=\sum\limits_{j=1}^iX_j$，那么对于所有 $1\le i\le |X|,1\le j\le N$ 的 $i,j$，都满足 $Y_i\not=A_j$

$1\le N\le 10^5$

$1\le A_1<A_2<\dots<A_N<S\le10^{18}$

发现 $Y_i$ 的奇偶性和 $i$ 的奇偶性相同，设 $dp_{i}$ 表示总和为 $i$ 的 $X$ 的个数，那么有转移：

$dp_{i}=\begin{cases}\sum\limits_{0\le j\le i-1,j\not\equiv i\pmod 2}dp_j&\nexists A_j=i\\0&\exists A_j=i\end{cases}$

这样做时间复杂度是 $O(S)$ 的，完美爆炸。考虑换一下 $dp$ 的定义，设 $dp_{0/1,i}$ 为总和是奇数/偶数，并且小于等于 $i$ 的方案数，那么有转移：

$\begin{cases} dp_{0,i}=dp_{0,i-1}+[i\operatorname{mod}2=0\land\nexists A_j=i]dp_{1,i-1}\\ dp_{1,i}=dp_{1,i-1}+[i\operatorname{mod}2=1\land\nexists A_j=i]dp_{0,i-1}\\ \end{cases}$

观察到对于所有满足 $A_j< i< A_{j+1}$ 的 $i$，$dp_{0/1,i}$ 的转移是完全不受到 $[\nexists A_j=i]$ 的影响的，这时有：

$\begin{cases} \begin{bmatrix}dp_{0,i-1},dp_{1,i-1}\end{bmatrix}\times \begin{bmatrix}1,1\\0,1\end{bmatrix}=\begin{bmatrix}dp_{0,i},dp_{1,i}\end{bmatrix}&i\operatorname{mod}2=1\\ \begin{bmatrix}dp_{0,i-1},dp_{1,i-1}\end{bmatrix}\times \begin{bmatrix}1,0\\1,1\end{bmatrix}=\begin{bmatrix}dp_{0,i},dp_{1,i}\end{bmatrix}&i\operatorname{mod}2=0 \end{cases}$

考虑把两次转移合并，有：

$\begin{cases} \begin{bmatrix}dp_{0,i-2},dp_{1,i-2}\end{bmatrix}\times \begin{bmatrix}1,1\\1,2\end{bmatrix}=\begin{bmatrix}dp_{0,i},dp_{1,i}\end{bmatrix}&(i-2)\operatorname{mod}2=1\\ \begin{bmatrix}dp_{0,i-2},dp_{1,i-2}\end{bmatrix}\times \begin{bmatrix}2,1\\1,1\end{bmatrix}=\begin{bmatrix}dp_{0,i},dp_{1,i}\end{bmatrix}&(i-2)\operatorname{mod}2=0\\ \end{cases}$

那么可以枚举 $j$，手动做一次转移，用矩阵乘法做 $A_{j+1}-A_j-1$ 次转移，再手动做一次转移即可。

时间复杂度 $O(N\log S)$。