ARC184E Accumulating Many Times 做题记录

对于一个长 $m$ 的 $01$ 序列 $a_{[1,m]}$，定义变换 $f$：

• $f(a)_i=\left(\sum\limits_{j\le i}a_j\right)\text{ mod 2}$；

也就是做一次异或意义下的前缀和。

对于两个长 $m$ 的序列 $a,b$，定义 $g(a,b)$ 为：

• 至少对 $a$ 做多少次变换 $f$ 才能令 $\forall i,a_i=b_i$，如果无论做多少次变换都不可能，那么 $g(a,b)$ 为 $0$；

现在给定 $n$ 个长 $m$ 的序列 $a_{[1,n]}$，求 $\sum\limits_{i<j}g(a_i,a_j)$，对 $998244353$ 取模。

$1\le n\times m\le 10^6$，$a_{i,j}\in \{0,1\}$。

对于一个序列 $a$，若其首位非 $1$ 则可以将首位删去，故下文默认 $a_{1}=1$。

不难发现，做 $k$ 次前缀和后 $a_i$ 对 $a_j$ 的贡献是 $\binom{k}{j-i}\text{ mod }2$。而根据 Lucas 定理，这个东西等于 $[j-i\subseteq k]$。

故 $a$ 的最小正周期 $T$ 为最小的 $\ge |a|$ 的 $2^x$。

对于两个序列 $a,b$，考虑如何判断 $a$ 能否到达 $b$。这类问题可以考虑代表元，只需找到 $a$ 和 $b$ 各自所在的环上的字典序最小的序列 $a_{\min},b_{\min}$ 并判断它们是否相等就行了。进一步，由于显然 $|a|=|b|$，那么它们的周期 $T$ 相等，只需找出 $a\to a_{\min}$ 和 $b\to b_{\min}$ 的步数 $ta,tb$，则：

$g(a,b)= \begin{cases} ta-tb & ta\le tb\\ T-ta+tb & ta>tb \end{cases}$

那么对于每个序列 $a_i$ 求出 $a_{\min}$，$T$ 和 $ta_i$ 后可以用树状数组简单计算答案。

现在来考虑 $a_{\min}$ 怎么求。根据 Lucas 定理，可以发现做 $2^k$ 次前缀和其实相当于做一次隔 $2^k$ 位的前缀和，即 $a_i$ 贡献到 $a_{i+2^k}$。

那么考虑从低往高确定 $ta_i$ 二进制的每一位，假设考虑到 $[2^k]ta_i$，则对于 $a_{1+2^k}$：

• $>k$ 的那些位影响不到它；
• $<k$ 的那些位对它的贡献已经确定了，假设影响为 $u$；

那么由于要最小化字典序，故可以确定 $[2^k]ta_i=a_{1+2^k}\oplus u\oplus 1$。

故这样扫一遍就可以确定 $ta_i$，从而确定 $a_{\min}$。

之后的部分都是简单的，时间复杂度 $O(nm\log n)$。