【双模数哈希】Binary String Copying
题意
小 C 获得了一个长度为 $ n $ 的 01 串 $ S $。
小 C 有 $ m $ 次操作,每次操作形如 $ [l,r] $,代表将 $ S $ 复制,生成一个 $ S $ 的副本,将副本 $ [l,r] $ 区间内数字字符从小到大排序,第 $ i $ 次操作生成的新串记为 $ S_i $。操作间互不影响,互相独立。
求出有多少不同的 $ S_i $。
多测,$ t $ 组数据。
$ 1 \le t \le 10^4 $,$ 1 \le \sum n,\sum m \le 2 \times 10^5 $。
思路
考虑如何方便地表示对 $[l,r]$ 排序后得到的新串 $t$,可以发现将串转化为一个哈希值比较好,在这里不妨直接将串看成数二进制表示,其代表的值就是哈希值。
假如要将 $s$ 的 $[l,r]$ 排序得到 $t$,则 $[1,l-1]$ 和 $[r + 1, n]$ 的哈希值都是可以预先预处理出来的,$[l,r]$ 段的哈希值也容易求,假设这一段有 $cnt$ 个 $1$,则其代表的值就是 $2^{cnt} - 1$。把这三段值拼起来就是 $t$ 串的哈希值了。
最终,通过哈希值判断不同的串即可。
为了尽可能避免哈希冲突,可以使用两个模数分别计算哈希值后判断。
代码
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const LL MOD1 = 1e9 + 9;
const LL MOD2 = 998244353;
const int N = 200010;
int T;
string s;
int cnt[N], n, m;
LL pre1[N], suf1[N], p1[N];
LL pre2[N], suf2[N], p2[N];
LL getValue1(int l, int r) {
LL preValue = pre1[l - 1];
LL sufValue = suf1[r + 1];
LL cnt1 = cnt[r] - cnt[l - 1];
LL len = r - l + 1;
LL midValue = ((p1[cnt1] - 1) % MOD1 + MOD1) % MOD1;
preValue *= p1[n - l + 1];
midValue *= p1[n - r];
preValue %= MOD1;
midValue %= MOD1;
return (preValue + midValue + sufValue) % MOD1;
}
LL getValue2(int l, int r) {
LL preValue = pre2[l - 1];
LL sufValue = suf2[r + 1];
LL cnt1 = cnt[r] - cnt[l - 1];
LL len = r - l + 1;
LL midValue = ((p2[cnt1] - 1) % MOD2 + MOD2) % MOD2;
preValue *= p2[n - l + 1];
midValue *= p2[n - r];
preValue %= MOD2;
midValue %= MOD2;
return (preValue + midValue + sufValue) % MOD2;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T--) {
cin >> n >> m >> s;
for (int i = 1; i <= n; i++) {
cnt[i] = cnt[i - 1] + (s[i - 1] == '1' ? 1 : 0);
}
pre1[0] = 0;
for (int i = 1; i <= n; i++) {
pre1[i] = 2 * pre1[i - 1] + (s[i - 1] - '0');
pre1[i] %= MOD1;
}
suf1[n + 1] = 0;
p1[0] = 1;
for (int i = 1; i <= n + 1; i++) {
p1[i] = p1[i - 1] * 2 % MOD1;
}
for (int i = n; i > 0; i--) {
suf1[i] = suf1[i + 1] + p1[n - i] * (s[i - 1] - '0');
suf1[i] %= MOD1;
}
pre2[0] = 0;
for (int i = 1; i <= n; i++) {
pre2[i] = 2 * pre2[i - 1] + (s[i - 1] - '0');
pre2[i] %= MOD2;
}
suf2[n + 1] = 0;
p2[0] = 1;
for (int i = 1; i <= n + 1; i++) {
p2[i] = p2[i - 1] * 2 % MOD2;
}
for (int i = n; i > 0; i--) {
suf2[i] = suf2[i + 1] + p2[n - i] * (s[i - 1] - '0');
suf2[i] %= MOD2;
}
set<LL> st1, st2;
LL res = 0;
while (m--) {
int l, r;
cin >> l >> r;
LL val1 = getValue1(l, r);
LL val2 = getValue2(l, r);
if (!st1.count(val1) || !st2.count(val2)) {
res++;
st1.insert(val1);
st2.insert(val2);
}
}
cout << res << "\n";
}
return 0;
}
补充
在实践时会发现,单模数判断总是会挂测试点,于是可以考虑写双模数哈希,进一步降低冲突概率。