[Math×Girl²] Theta's Theory 题解

· · 题解

转化的部分就不讲了，可以看其他题解，这里提供另一种思路，虽然感觉本质是一样的。

首先直接快进到优化转移的部分，

f_i(h) = [\text{ok}(S_i, h)] \sum_t \binom{\lceil \frac{h}{2}\rceil}{h-t} f_{i+1}(t)

其中

\text{ok}(S_i, h) = \begin{cases} 1, & S_i = ? \\ 1, & S_i = h \bmod 2 \\ 0, & \text{otherwise}. \end{cases}

但是由于这个讨厌的 \lceil \frac{h}{2}\rceil 的存在，导致不能直接拆开做卷积。

抛弃掉 \text{ok}(S_i,h) 只考虑一次转移。先对奇偶分类，写成

g_{2q}=\sum_t \binom{q}{2q-t}f_t

定义线性泛函 \mathcal{L}(x^t)=f_t，即 \mathcal{L}(\sum p_tx^t)=\sum p_tf_t

左边的组合数容易写出 GF 为 x^q(1+x)^q，那其实就是要求 \mathcal{L}((x^2+x)^q)。

但是这个东西不太好直接算，考虑换元配方，令 y=x+\frac{1}{2}，那么就是要求 \mathcal{L}((y^2-\frac{1}{4})^q)，但是这里请注意 \mathcal{L}(y^t)\ne f_t，因为 \mathcal{L}(y^t)=\mathcal{L}((x+\frac{1}{2})^t)，展开得

h_t=\mathcal{L}(y^t)=\sum_{i=0}^t \binom{t}{i}f_i(\frac{1}{2})^{t-i}

而这个东西就可以直接卷了。

而 \mathcal{L}((y^2-\frac{1}{4})^q) 这个也可以直接展开算了，就是

\sum_{i=0}^q \binom{q}{i}h_{2i}(-\frac{1}{4})^{q-i}

这个直接卷就行了。奇数也是一样的处理即可。