题解：P17228 [Math×Girl²] Theta's Theory
Galois_Field_1048576
·
·
题解
声明: 写作过程中多次使用 AI 检验并修改病句、斟酌用词与行文,
论证的展开亦有 AI 参与;
思路均出自魔女の理团队的各出题人、验题人及我的个人理解.
总结. 先反转操作序列, 将合法性改写为 “值为 x 的操作必在偶数位置”;
给定串再限制相应的奇偶性; 最后用提取对角项的算子 D 将动态规划优化至
**题目描述.** 对于一个二进制串 $s$, 定义 $s$ 的一次操作为: 选取一个自然数 $i$ 使得
$s_i = 0$, 将 $s$ 异或上一个 $11\cdots100\cdots0$ (从低位到高位),
其中最后一个 $1$ 的下标为 $i$. 定义 $f_s(m)$ 为在 $m$ 次操作内把 $s
变成全 1 串的方案数. 现在给定一个由 0, 1, ? 组成的串 t, 记 T
为把 t 中每个 ? 替换成 0 或 1 所得的全部串. 求
设一共进行了 $k$ 次操作, 依次为 $a_0, a_1, \dots, a_{k-1}$, 并设
$$b_i = \left\lvert\{ j : a_j \ge i \}\right\rvert.$$ 初始的 $s_i
被翻转了 b_i 次, 故 s_i = (b_i \bmod 2) \oplus 1.
先给出一个多项式算法. 为此, 先解决 t = \texttt{????...??} 的情形.
把操作序列倒过来看, 相当于从 1111...11 出发构造 s: 令
得到序列 $\sigma$, 其长度为 $b_x$.
**定理 E.1.** 存在某个 $s$, 使得依次执行操作 $a_0, a_1, \dots, a_{k-1}$ 后得到
`1111...11`, 当且仅当对每个 $x$, $\sigma$ 中所有值为 $x
的元素都位于偶数位置.
证明. 细看正向序列中任意一次位置为 x 的操作, 设在此次操作之前,
位置不小于 x 的操作已经出现过 p 次. 此时位置 x 被翻转了 p 次, 故
$p \equiv b_x + 1 \pmod 2$. 在反转前的序列中, 这次操作是位置不小于 $x
的操作中的第 p 个, 故在反转后的 \sigma 中它排在第 b_x - 1 - p 位,
为偶数位置. 反过来, 由 s_x = (b_x \bmod 2) \oplus 1 与
$\blacksquare
假设大于 x 的操作已经全部构造好, 共 b_{x+1} 个元素; 现在加入
其中偶数位置有 $\left\lceil \dfrac{b_x}{2} \right\rceil$ 个,
从这些位置中选 $b_x - b_{x+1}$ 个来放置新元素, 方案数为
$$\binom{\left\lceil \dfrac{b_x}{2} \right\rceil}{b_x - b_{x+1}}.$$
对所有满足 $n = b_0 \ge b_1 \ge \cdots \ge b_n = 0$ 的序列求和,
用动态规划即可在多项式时间内算出该和.
再看给定串 $t$ 的限制, 按 $t_i$ 的取值分类讨论:
- 若 $t_i = \mathtt{1}$, 则要求 $b_i$ 为偶数;
- 若 $t_i = \mathtt{0}$, 则要求 $b_i$ 为奇数;
- 若 $t_i = \texttt{?}$, 则无限制.
枚举 $b_i$ 时只需取满足相应限制的值. 动态规划如下: 设 $F(i+1, x)
为已处理完位置 i+1, i+2, \cdots, n-1, 且这些位置上的操作总数为 x (即
b_{i+1} = x$) 的方案数. 状态转移为: 对满足 $x+c \equiv t_i + 1 \pmod 2
的 c (当 t_i = \texttt{?} 时不加限制),
F(i,x+c) \gets F(i,x+c) + F(i+1,x) \cdot \binom{\left\lceil (x+c)/2 \right\rceil}{c}.
目前的时间复杂度为 \mathrm O(n \cdot m^2).
下面用多项式方法优化. 取 p_i(z) = \sum_{k \ge 0} F(i,k) z^k, 设
$$v_i = [i\ \text{合法}] \cdot \sum_{j=0}^i u_j \binom{\lceil i/2 \rceil}{i-j}.$$
对于按奇偶性分类的下标 $i = 2p, 2p+1$, $$\begin{aligned}
v_{2p} = [2p\ \text{合法}] \cdot \sum_{x=0}^{2p} u_{x} \binom{p}{2p-x} = [2p\ \text{合法}] \cdot \sum_{x = 0}^p \binom px u_{p+x} \\
v_{2p+1} = [2p+1\ \text{合法}] \cdot \sum_{x=0}^{2p+1} u_{x} \binom{p+1}{2p+1-x} = [2p+1\ \text{合法}] \cdot \sum_{x = 0}^{p+1} \binom{p+1}x u_{p+1+x}.
\end{aligned}$$
为此, 提取形如 $\binom rk u_{r+k}$ 的求和项, 定义算子:
$$
D\left(\sum_{k \ge 0} c_k z^k\right) = \sum_{r \ge 0} \sum_{k=0}^r \binom rk c_{r+k} z^r.
$$
暂且忽略表示合法性的 Iverson 括号, 有 $v_{2p} = [z^p]\,D(p_{i+1})$,
$v_{2p+1} = [z^{p+1}]\,D(z \cdot p_{i+1})$.
下面推导 $D$ 的代数表示. 由于
$$\dfrac{1}{1-zx(1+x)} = \sum_{r \ge 0} z^r x^r (1+x)^r,$$ 所以
$$[x^r] \dfrac{1}{1-zx(1+x)} = \sum_{k=0}^{\lfloor r/2 \rfloor} \binom{r-k}{k} z^{r-k}.$$
用提取对角项的方法, 可得恒等式
$$D(F) = [x^0] \dfrac{F(x^{-1})}{1-zx(1+x)}.$$
再定义分别嵌入偶数次项和奇数次项的两个算子: $$\begin{aligned}
\alpha : H(z) \mapsto H(z^2) \quad z^0 \mapsto z^0, z^1 \mapsto z^2, z^2 \mapsto z^4 \cdots; \\
\beta : H(z) \mapsto \dfrac{H(z^2) - H(0)}{z} \quad z^1 \mapsto z^1, z^2 \mapsto z^3, z^3 \mapsto z^5 \cdots.
\end{aligned}$$
组合起来, 有
$$p_i = [0\ \text{合法}] \cdot \alpha(D(p_{i+1})) + [1\ \text{合法}] \cdot \beta(D(z\,p_{i+1})),$$
其中 $[0\ \text{合法}]$、$[1\ \text{合法}]
分别表示偶数位置、奇数位置的合法性条件.
关键在于快速计算 D. 做部分分式分解
$\lambda, \mu$ 是 $X^2 - zX - z = 0$ 的根. 则有
$$D(F) = \frac{1}{\lambda-\mu} [x^0] \left( \frac{\lambda F(x^{-1})}{1-\lambda x} -
\frac{\mu F(x^{-1})}{1-\mu x} \right).$$ 化简得到
$$D(F) = \dfrac{\lambda F(\lambda) - \mu F(\mu)}{\lambda - \mu}.$$
观察到 $\lambda^2-z\lambda-z=0$ 可解出 $z=\dfrac{\lambda^2}{1+\lambda}$,
另一根为 $\mu=-\dfrac{\lambda}{1+\lambda}$. 做代换 $t=\lambda$, 则
$z=\dfrac{t^2}{1+t}$, 且
$$D(F)(z)=\frac{(1+t)F(t)+F\!\left(-\frac{t}{1+t}\right)}{t+2} =: G(t).$$
记 $\phi(t)=\frac{t^2}{1+t}$, 则 $D(F)(\phi(t))=G(t)$. 问题归结为: 给定
$G(t)$, 求 $H(z)$ 使得 $H(\phi(t))=G(t)$ (这里 $H(z)$ 就是所求的
$D(F)(z)$).
由 $G(t^{-1})=H\bigl(\frac{1}{t(t+1)}\bigr)$ 出发. 若 $\deg H=d$, 记
$H^\ast(z)=z^dH(z^{-1})$, 即将 $H$ 的系数按次数倒序排列; $G^\ast
同样定义. 于是 H^\ast(t^2+t)=G^\ast(t). 配方
$H^\ast(u^2-\frac14)=G^\ast(u-\frac12)$. 取平方根复合逆
$u=\sqrt{v+\frac14}$, 得
$$H^\ast(v)=G^\ast\!\left(\sqrt{v+\tfrac14}-\tfrac12\right),$$
最后将系数倒序排列, 即恢复 $H$. 平移、开方、复合都可在 $O(\mathsf M(m))
时间内完成, 故单次 D 算子可在 O(\mathsf M(m)) 内计算, 总复杂度为