ABC258Ex Odd Steps 做题记录

给定 NNSS 和长度为 NN 的序列 AA,找到满足以下条件的序列 XX 的个数对 998244353998244353 取模后的结果:

  • XX 的每个元素都是正奇数
  • Xi=S\sum X_i=S
  • Yi=j=1iXjY_i=\sum\limits_{j=1}^iX_j,那么对于所有 1iX,1jN1\le i\le |X|,1\le j\le Ni,ji,j,都满足 Yi=AjY_i\not=A_j

1N1051\le N\le 10^5

1A1<A2<<AN<S10181\le A_1<A_2<\dots<A_N<S\le10^{18}

发现 YiY_i 的奇偶性和 ii 的奇偶性相同,设 dpidp_{i} 表示总和为 iiXX 的个数,那么有转移:

dpi={0ji1,ji(mod2)dpjAj=i0Aj=idp_{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)O(S) 的,完美爆炸。考虑换一下 dpdp 的定义,设 dp0/1,idp_{0/1,i} 为总和是奇数/偶数,并且小于等于 ii 的方案数,那么有转移:

{dp0,i=dp0,i1+[imod2=0Aj=i]dp1,i1dp1,i=dp1,i1+[imod2=1Aj=i]dp0,i1\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}

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

{[dp0,i1,dp1,i1]×[1,10,1]=[dp0,i,dp1,i]imod2=1[dp0,i1,dp1,i1]×[1,01,1]=[dp0,i,dp1,i]imod2=0\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}

考虑把两次转移合并,有:

{[dp0,i2,dp1,i2]×[1,11,2]=[dp0,i,dp1,i](i2)mod2=1[dp0,i2,dp1,i2]×[2,11,1]=[dp0,i,dp1,i](i2)mod2=0\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}

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

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