P11404 [RMI 2020] 蝶变 题解

Description

定义一个长度为 $2^k$ 的序列 $[a_0,a_1,\cdots,a_{2^k-1}]$ 蝶变之后的结果为 $[a_{\operatorname{rev}(0)},a_{\operatorname{rev}(1)},\cdots,a_{\operatorname{rev}(2^k-1)}]$，其中 $\operatorname{rev}(i)$ 表示将 $i$ 的二进制表示下最低 $k$ 位翻转（reverse）后得到的结果。更为具体地说，令 $i=\overline{b_kb_{k-1}\cdots b_1}$，则 $\operatorname{rev}(i)=\overline{b_1b_{2}\cdots b_k}$。

定义一个长度为 $2^k$ 的序列是美的，当且仅当蝶变后的序列与原序列相同。

给定一个长度为 $N$ 的字符串 $s$，字符集为小写英文字母。$Q$ 次询问给定 $i,k$，问 $s[i:i+2^k-1]$ 是否是美的。

$1\le N,Q\le 5\times 10^5$。

Solution

首先显然是用哈希判定。

设 $f_k(i,B)$ 表示 $[a_i,a_{i+1},\ldots,a_{i+2^k-1}]$ 变换后的底数是 $B$ 的哈希值，可以得到方程：

$$f_k(i,B)=f_{k-1}(i,B^2)+B\cdot f_{k-1}(i+2^{k-1},B^2)$$

观察到只有 $O(\log n)$ 种底数，所以可以得到一个时空 $O(n\log^2n)$ 的做法。

但是注意到区间长度除以 $2$ 后指数会乘 $2$，所以可以将 $f_k(i,B)$ 的指数固定为 $B^{2^{25-k}}$，这样每次就可以 $O(1)$ 转移了。

时间复杂度：$O(n\log n)$。

Code

#include <bits/stdc++.h>
#include "brperm.h"

#ifdef ORZXKR
#include "grader.cpp"
#endif

const int kMaxN = 5e5 + 5, kMod = 998244353;

int n, base = 114514;
int bs[20], hs[20][kMaxN], f[20][kMaxN];
std::string str;

int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

void init(int n, const char s[]) {
  ::n = n;
  str.resize(n + 1);
  for (int i = 1; i <= n; ++i) str[i] = s[i - 1];
  for (int i = 0; i <= 19; ++i) {
    bs[i] = qpow(base, 1 << (30 - i));
    for (int j = 1, pw = bs[i]; j <= n; ++j, pw = 1ll * pw * bs[i] % kMod)
      hs[i][j] = add(hs[i][j - 1], 1ll * pw * (int)str[j] % kMod);
  }
  for (int i = 1; i <= n; ++i) f[0][i] = str[i];
  for (int i = 1; i <= std::__lg(n); ++i)
    for (int j = 1; j <= n - (1 << i) + 1; ++j)
      f[i][j] = add(f[i - 1][j], 1ll * bs[i] * f[i - 1][j + (1 << (i - 1))] % kMod);
}

int query(int i, int k) {
  ++i;
  if (k > std::__lg(n - i + 1)) return 0;
  return 1ll * sub(hs[k][i + (1 << k) - 1], hs[k][i - 1]) * qpow(qpow(bs[k]), i) % kMod == f[k][i];
}