P7350 题解
yzy1
·
·
题解
我怎么感觉这个 D 比 A 简单？好吧原来 D 才是这场比赛签到题。
题目大意
给定正整数 b,p 和字符串 S。构造一个字符集为 [\tt a,z]，长度为 |S| 的字符串 T，满足 S\ne T 且两个字符串对进行进制为 b、模数为 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，所以这种随机化算法成功率相当高。
## 参考代码
```cpp
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]$。