ARC184E

lsj2009 · 2024-12-20 15:42:17 · 题解

Description

给定 n 个长为 m 的 \tt 01 串 A_{1\sim n}，定义 f(i,j) 表示最小的 k 使得 A_i 的 k 次异或前缀和等于 A_j，若不存在则令 f(i,j)=0。

求 \left(\sum\limits_{1\le i\le j\le n}f(i,j)\right)\bmod{998244353}。

Solution

异或前缀和性质没有异或差分好（因为前缀和与 1\sim j 均相关，差分之和 j-1,j 相关，或者这从后文可以更自然地表现出来），故我们转换为每次对 A_j 进行 差分 操作，求最小操作次数使得 A_j=A_i。

将问题刻画在图论上，记对于 A 进行差分操作得到 \Delta A（进行 k 次操作得到 \Delta^k A），则连边 A\to \Delta A。

我们发现：每个 A 存在唯一的出边和入边。前者显然，后者因为 \Delta B=A 是有唯一解的，因为 B 也就是 A 的异或前缀和数组。

也就是：我们建出来的图必然由若干个环组成。

则 f(A_i,A_j) 为路径 A_j\to A_i 在环上的长度，如果两者不在同一环内则为 0。

下面便于讨论，假设所有 A_i 均在同一置换环内，若不在则对于每个置换环求解即可。

我们考虑取出环上的一个 代表点 C 以及环长 \ell，求出 d_i=\operatorname{len}(C\to A_i)\le len，则 f(i,j)=(d_i-d_x)\bmod{\ell}。

从小到大扫描 i，然后把他加入集合 S，每次即求出 \sum\limits_{x\in S}(d_i-d_j)\bmod{\ell} 然后求和，对于 d_i\ge d_j 和 d_i<d_j 分别计算贡献，容易使用树状数组维护，复杂度 \mathcal{O}(n\log{n})。

问题在于如何求出 d_i 和 \ell。

不妨取代表点 C 为环上 字典序最小的点。

我们将差分刻画为多项式乘法的形式：

这里多项式 F(x)=G(x)\bmod{2} 的含义是按位取模（进行加法时就是进行异或），即得到 F(x)=\sum\limits ([x^i]G(x)\bmod{2})x^i。

进一步得 \Delta^k A=(1+x)^kA\pmod{2}。

考虑拆分：k=\sum\limits 2^{p_i}，即得到 \Delta^k A=\left(\prod(1+x)^{2^{p_i}}\right)A。观察 (1+x)^{2^{p_i}}：

其中用到了 Lucas 定理的推论：\binom{n}{m}\equiv[m\subseteq n]\pmod{2}。

所以 \Delta^k A=\left(\prod\left(1+x^{2^{p_i}}\right)\right)A。

找到 A 首个 1 的位置 t（特判全 0），则 t 始终为 1，发现若进行 \Delta^{2^p} 操作，则 A_{t+2^p} 必然是首个发生变化的位置，且有 p_1<p_2\Rightarrow t+2^{p_1}<t+2^{p_2}，即 越小的 p 优先级越高。

所以我们 从小往大枚举 p，每次依据当前 A_{t+2^p} 值考虑是否进行 \Delta^{2^p} 操作，最终 d_i=\sum 2^{p_i}。进行一次操作暴力更新就是 \mathcal{O}(m) 的，显然有 p\le\lfloor\log{m-t}\rfloor，所以这一部分复杂度就是 \mathcal{O}(nm\log{m})，可以接受。

然后是如何求出 \ell，那我们接受要找到那个最不牛的点，也就是 \ell=\max d+1，那就是 每次都进行操作（并且根据操作还原回去，显然存在这样子的点），共进行 \lfloor\log{m-t}\rfloor 次操作，所以 \ell=\left(\sum\limits_{i=0}^{\lfloor\log{m-t}\rfloor} 2^i\right)+1=2^{\lfloor\log{m-t}\rfloor+1}。

然后就解决了所有问题，复杂度 \mathcal{O}(nm\log{m}+n\log{n})。

code link。