题解：P11404 [RMI 2020] 蝶变 / Brperm

· · 题解

题目链接：P11404 [RMI 2020] 蝶变 / Brperm

:::info[题外话]{open} 这道题放到了我们的 NOIP 模拟赛中，也是给我看懵了，发现不了一点性质，只会打个暴力。结束后题解说这是什么“蝴蝶变换”。但是“蝴蝶变换”这个点貌似主要用到诸如快速傅里叶变换的多项式中？我也不知道，我不会多项式。所以应用到字符串的这种情况还是挺少见的，挺好一题。但是我实在看不懂老师给的题解，于是在同学 bhs 的讲解下有了这篇题解。 :::

:::info[推导过程]

我先来解释一下题面传达的意思。

假设我们现在有一个长度为 2^k 的数组：

A = [a_0, a_1, \ldots, a_{2^k-1}]

蝶变的定义是：

A'[i] = A[\operatorname{rev}_k(i)]

其中 \operatorname{rev}_k(i) 表示把 i 的二进制低 k 位翻转。

举个栗子。例如 k=3：

i i 的二进制 \operatorname{rev}_3(i)
0 000 000
1 001 100
2 010 010
3 011 110
4 100 001
5 101 101
6 110 011
7 111 111

此时我们进行蝶变之后的数组为：

A' = [a_0, a_4, a_2, a_6, a_1, a_5, a_3, a_7]

我们现在设原数组的下标为：

j = (b_{k-1}b_{k-2}\cdots b_1b_0)_2

那么它的蝶变下标即为：

\operatorname{rev}_k(j) = (b_0b_1\cdots b_{k-2}b_{k-1})_2

到这里，运用我们惊人的注意力，可以发现，原下标的最低位 b_0，翻转之后跑到了最高位。也就是说：

所以我们现在发现了一个性质：

j \equiv 0 \pmod 2 \iff \operatorname{rev}_k(j) < 2^{k-1} j \equiv 1 \pmod 2 \iff \operatorname{rev}_k(j) \ge 2^{k-1}

那么这意味着，原数组的偶数位置，蝶变之后会落在前半部分；原数组的奇数位置，蝶变之后会落在后半部分。因此我们可以考虑将原数组按照奇偶拆分。

我们再把原数组按照奇偶拆分。具体地，我们定义：

E = [a_0, a_2, a_4, \ldots] O = [a_1, a_3, a_5, \ldots]

很明显，它们的长度都是 2^{k-1}。

现在我们来证明：

\operatorname{rev}_k(A) = \operatorname{rev}_{k-1}(E) + \operatorname{rev}_{k-1}(O)

证明如下：

我们上面说到，原数组偶数位置的元素，蝶变后一定落在前半部分。设偶数位置对应的原下标为 j = 2t。那么：

j = (b_{k-1}\cdots b_1 0)_2

翻转后：

\operatorname{rev}_k(j) = (0b_1\cdots b_{k-1})_2

去掉最前面的 0，剩下的为：

(b_1b_2\cdots b_{k-1})_2

而这恰好就是 \operatorname{rev}_{k-1}(t)。因此：

\boxed{ \operatorname{rev}_k(2t) = \operatorname{rev}_{k-1}(t) }

因此蝶变结果的前半部分，恰好是 E 进行 k-1 位蝶变的结果。

同理，原数组奇数位置的元素，蝶变后一定落在后半部分。我们继续设原下标 j = 2t + 1。 那么：

j = (b_{k-1}\cdots b_1 1)_2

同样进行翻转后变为：

\operatorname{rev}_k(j) = (1b_1\cdots b_{k-1})_2

它的最高位是 1，所以对应后半部分。去掉最高位的 1，剩下的部分恰好是 \operatorname{rev}_{k-1}(t)。因此：

\boxed{ \operatorname{rev}_k(2t+1) = 2^{k-1} + \operatorname{rev}_{k-1}(t) }

我们可以看出来，蝶变结果的后半部分，恰好是 O 进行 k-1 位蝶变的结果。

我们将上面两部分合起来：

\boxed{ \operatorname{rev}_k(A) = \operatorname{rev}_{k-1}(E) + \operatorname{rev}_{k-1}(O) }

证毕。

我们定义普通字符串哈希：

H(A) = \sum_{i=0}^{n-1} \operatorname{val}(A_i) B^{n-1-i}

其中 B 就是哈希进制，\operatorname{val}(c) 是字符对应的整数啦。这是哈希对应的公式，没什么好说的。

我们假设两个字符串 X,Y 长度分别为 n,m，那么拼接哈希满足：

\boxed{H(X+Y) = H(X)B^m + H(Y)}

这也是字符串哈希的基础公式，并且很显然，在此不再解释了。

因此我们可以类比的得到：

H(\operatorname{rev}_k(A)) = H(\operatorname{rev}_{k-1}(E(A))) B^{2^{k-1}} + H(\operatorname{rev}_{k-1}(O(A)))

那么现在蝶变哈希递推式就顺利地推出来了。

最后只需要判断原数组的哈希值与进行蝴蝶变换后的数组哈希值是否相等即可。

到这里，我们可以发现一个问题：E(A) 和 O(A) 并不是原字符串中的连续子串。普通的字符串哈希只能 O(1) 查询连续子串，不能直接查询这种隔一个字符取一个的序列。所以我们现在还需要思考一下怎么解决这个问题。

我们考虑定义：

\boxed{f_{k, d, i}}

表示从位置 i 开始，每隔 2^d 个位置取一个字符，一共取 2^k 个字符，对这个序列进行蝶变后的哈希值。

它对应的原始序列是：

[s_i, s_{i+2^d}, s_{i+2 \cdot 2^d}, \ldots]

按照上面我们推导的，把它拆成奇偶位置：

然后我们就会发现：

根据我上面写出的字符串拼接哈希公式得到：

f_{k, d, i} = f_{k-1, d+1, i} \cdot B^{2^{k-1}} + f_{k-1, d+1, i+2^d}

当 k=0 时，序列长度只有 1。一个字符进行蝶变后还是自己。所以初始状态为：

f_{0, d, i} = \operatorname{val}(s_i)

这样就可以解决上面的问题啦。

但我们发现这样开数组空间会直接爆掉。可以发现，计算 f_{k,d} 时，只需要用到 f_{k-1,d+1}。也就是说，每次转移时，k 减少 1，而 d 增加 1，因此 k+d 始终保持不变。

那么，对于每个固定的 k，我们实际上只需要计算：

f_{0,k}\rightarrow f_{1,k-1}\rightarrow f_{2,k-2}\rightarrow\cdots\rightarrow f_{k,0}

也就是沿着 k+d 固定的这条对角线进行计算，而其他状态都不会参与最终答案的转移，没有必要计算和保存。

进一步地，由于计算当前层时只需要上一层的结果，因此我们不必保存整条对角线上的所有状态，只需要使用两个数组分别维护上一层和当前层的结果，每次计算完成后交换两个数组即可。

这样我们就可以解决空间问题啦。

最后我们只需要预处理一下普通字符串哈希：

\operatorname{pre}_{i+1} = \operatorname{pre}_{i} \cdot B + \operatorname{val}_{s_i}

那么长度为 2^k、起点为 i 的子串哈希为：

\boxed{ H(i, k) = \operatorname{pre}_{i+2^k} - \operatorname{pre}_{i} \cdot B^{2^k} }

而我们预处理得到的蝶变哈希是 f_{k, 0, i}。因此，对于每一次询问，最终的判断为：

\boxed{ \operatorname{query}(i, k) = \begin{cases} 0 & i+2^k > N \\ 1 & H(i, k) = f_{k, 0, i}\\ 0 & H(i, k) \ne f_{k, 0, i}\end{cases} }
这里我们一般使用双模哈希来降低哈希冲突的概率。

:::info[复杂度分析]

我们令 K = \lfloor\log_2 N\rfloor：

因此，我们最终的时间复杂度为 O(N \log^2 N + Q)，空间复杂度为 O(N \log N)。

:::

以上就是本道题的全部推导过程啦，下面给出参考代码。

:::success[参考代码]

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 500010;
const int K = 20;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
const int B1 = 911382323;
const int B2 = 1331;

int n;
int pw1[K], pw2[K];
int pre1[N], pre2[N];

struct Hash
{
    int x, y;
} dp[N], ndp[N], ans[K][N];

void init(int N, const char s[])
{
    n = N;

    pw1[0] = B1;
    pw2[0] = B2;

    for (int i = 1; i < K; i++)
    {
        pw1[i] = 1ll * pw1[i - 1] * pw1[i - 1] % MOD1;
        pw2[i] = 1ll * pw2[i - 1] * pw2[i - 1] % MOD2;
    }

    pre1[0] = pre2[0] = 0;

    for (int i = 0; i < n; i++)
    {
        int x = s[i] - 'a' + 1;

        pre1[i + 1] = (1ll * pre1[i] * B1 + x) % MOD1;
        pre2[i + 1] = (1ll * pre2[i] * B2 + x) % MOD2;
    }

    int mx = 0;

    while ((1 << (mx + 1)) <= n) mx++;

    for (int k = 1; k <= mx; k++)
    {
        Hash *cur = dp, *nxt = ndp;

        for (int i = 0; i < n; i++)
        {
            dp[i].x = s[i] - 'a' + 1;
            dp[i].y = s[i] - 'a' + 1;
        }

        for (int r = 1; r <= k; r++)
        {
            int step = 1 << (k - r);
            int ed = n - (1 << k) + step - 1;

            for (int i = 0; i <= ed; i++)
            {
                nxt[i].x = (1ll * cur[i].x * pw1[r - 1] + cur[i + step].x) % MOD1;
                nxt[i].y = (1ll * cur[i].y * pw2[r - 1] + cur[i + step].y) % MOD2;
            }

            swap(cur, nxt);
        }

        for (int i = 0; i + (1 << k) <= n; i++) ans[k][i] = cur[i];
    }
}

int query(int i, int k)
{
    int len = 1 << k;

    if (i + len > n) return 0;
    if (k == 0) return 1;

    int x = (pre1[i + len] - 1ll * pre1[i] * pw1[k] % MOD1 + MOD1) % MOD1;
    int y = (pre2[i + len] - 1ll * pre2[i] * pw2[k] % MOD2 + MOD2) % MOD2;

    return x == ans[k][i].x && y == ans[k][i].y;
}

:::

以上为本篇的全部内容，感谢您的耐心阅读，希望本篇文章对您有所帮助。