自动搬运

查看原文

来自洛谷，原作者为

	yzy1 Меня мое сердце, в тревожную даль зовёт.

搬运于2025-08-24 22:29:01，当前版本为作者最后更新于2022-01-13 13:36:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我怎么感觉这个 D 比 A 简单？好吧原来 D 才是这场比赛签到题。

题目大意

给定正整数 $b,p$ 和字符串 $S$。构造一个字符集为 $[\tt a,z]$，长度为 $|S|$ 的字符串 $T$，满足 $S\ne T$ 且两个字符串对进行进制为 $b$、模数为 $p$ 的单哈希后得到的结果相等。

$50\le |S| \le 10^5$，$257 \le b \le p \le 10^9+9$ 且 $p$ 为质数。

大体解法

首先这题肯定 $|S|$ 越大越好做，所以只要考虑 $|S|=50$ 的情况。首先预处理出一个 $50$ 位全是 a 的字符串的 hash 值和 $b^k \bmod p$ 的结果。问题转化为你要构造一个长度为 $50$ 且每一位 $\in [0,25]$ 的整数数列，满足 $\sum_{i=0}^{49} a_ib^k = H$。

考虑构造一堆 $50$ 位的 $01$ 串 mask。mask 每一位为 $1$ 代表把这一位的字符串 ASCII $+1$，每生成一个跟现有的所有 mask 匹配一下，匹配的过程就是对于每一位 $i$，令 $T_i \gets a_i+b_i + \mathtt{'a'}$，生成一个字符集为 $[\tt a,c]$ 的字符串，匹配可以直接 $O(1)$ 查 unordered_map，看看能不能构造出题目给定的 hash。

由于随机 $N$ 个 mask 可以生成 $O(N^2)$ 个不同的 hash，所以这种随机化算法成功率相当高。

参考代码

const int N = 2e5 + 9;
const ull MASK = (1ull << 50) - 1;
int b, mo, n, need, bpw[N];
char s[N];
unordered_map<ull, ull> mp;
mt19937_64 rnd;

void Out(ull x, ull y) {
  re (i, n - 50)
    cout << s[i];
  per (i, 49, 0)
    cout << char('a' + ((x >> i) & 1) + ((y >> i) & 1));
}

signed main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> b >> mo >> (s + 1), n = strlen(s + 1);
  bpw[0] = 1;
  re (i, 55)
    bpw[i] = 1ll * bpw[i - 1] * b % mo;
  rep (i, n - 49, n)
    need += 1ll * bpw[n - i] * (s[i] - 'a') % mo, umod(need);
  while (1) {
    ull x = rnd() & MASK;
    int ha = 0;
    rep (i, 0, 49)
      ha += ((x >> i) & 1) * bpw[i], umod(ha);
    mp[ha] = x;
    if (mp.count((need - ha + mo) % mo)) Out(x, mp[(need - ha + mo) % mo]), exit(0);
  }
  return 0;
}

好像被 w33z hack 了？没关系，可以把代码中的字符 a 全都改成一个 $[\tt a,x]$ 范围内的随机字符，设这个字符为 $C$，则构造出来的字符串字符集为 $[C,C+3]$。