Gym103409H Popcount Words 解题报告

2022-01-24

值得借鉴的神仙倍增思路。

发现 $\text{popcount}(x) \bmod 2$ 有倍增对称性。记原题 $w(0,2^k-1)$ 表示的串为 $w_{k,0}$，$w(0,2^k-1)$ 按位取反表示的串为 $w_{k,1}$，有下列递推式：

$w_{0,0}=0,w_{0,1}=1\\ w_{i,0}=w_{i-1,0}+w_{i-1,1}\\ w_{i,1}=w_{i-1,1}+w_{i-1,0}$

由上式可知：任意 $w(l,r)$ 都可以由 $\log r$ 个 $w$ 串相加得到。

将原题 $n$ 个区间分解，得到 $n\log V$ 个区间 $w_{k,i}$。

对于所有询问串，建立 AC 自动机，基本的做法是将原串 $S$ 在 AC 自动机上跑一遍，统计每个询问串对应节点 fail 树的子树和。

本题不能暴力将串 $S$ 输入进自动机，但字符串具有可倍增的性质，考虑 dp。设 $f_{0/1,k,u}$ 为当前在 $u$ 节点，在 AC 自动机上继续走 $2^k$ 个节点，$0/1$ 代表当前走的串是 $w_{k,0}$ 还是 $w_{k,1}$，能到达哪个节点，倍增转移。

有了 $f$ 数组，我们可以利用类似打标记的思想，设 $g_{0/1,k,u}$ 为有多少个区间 $w_{k,0/1}$ 以 $u$ 为起点，倒序倍增下传标记。最后对于每个自动机上的节点 $u$，答案为 $g_{0,0,u}+g_{1,0,u}$。最后输出作为询问串结尾节点 fail 树子树的点权和即可。

核心代码如下：

分解 $w(l,r)$：

void split(int l, int r, int ql, int qr, int coef){
    if(ql == l && r == qr) return vec.push_back(make_pair(coef & 1, __lg(qr - ql + 1))), void();
    int mid = (l + r) >> 1;
    if(qr <= mid) split(l, mid, ql, qr, coef);
    else if(ql > mid) split(mid + 1, r, ql, qr, coef + 1);
    else split(l, mid, ql, mid, coef), split(mid + 1, r, mid + 1, qr, coef + 1);
}

$f$ 数组的倍增转移：

for(int i = 0; i <= tot; ++i) f[0][0][i] = ch[i][0], f[1][0][i] = ch[i][1];
for(int i = 1; i <= 29; ++i){
for(int j = 0; j <= tot; ++j){
        f[0][i][j] = f[1][i - 1][f[0][i - 1][j]];
        f[1][i][j] = f[0][i - 1][f[1][i - 1][j]];
    }
}

$g$ 数组的倍增转移：

for(int i = 29; i >= 1; --i){
    for(ll j = 0, t; j <= tot; ++j){
        if(t = g[0][i][j]) g[0][i - 1][j] += t, g[1][i - 1][f[0][i - 1][j]] += t;
        if(t = g[1][i][j]) g[1][i - 1][j] += t, g[0][i - 1][f[1][i - 1][j]] += t;
    }
}

Solutions

Welcome!

Hang around and make yourself at home.

Updates may be slow

Due to unstable connection to GitHub, blog posts may not be up-to-date.