标题本来叫「哈希」，后来发现第二天的很多题虽然打了哈希的 tag 但是只有 KMP 做法，故忍痛改成「字符串」。
A. Two Permutations
http://222.180.160.110:61235/contest/5653/problem/1
有个很重要的性质是 \(a\) 和 \(b\) 都是排列。然后我们就知道了 \(x\in [0,m-n]\)，且每个 \(a_i+x\) 在 \(b\) 中有元素与之唯一对应。于是问题可以转化成，\(b\) 中在 \([1+x,n+x]\) 范围中的元素按顺序哈希起来和 \(a\) 序列是否完全一致。
我们就有了一个想法：枚举这个 \(x\)，通过某种方法快速查询这个长度固定的值域区间按顺序哈希起来的值。然后就是典中典之线段树维护哈希，只需在枚举 \(x\) 时滑动窗口，剔除头部元素，新增尾部元素，查询全局哈希值即可。
还有一个小细节是关于实时维护全局加 \(x\) 后的 \(a\)。由于哈希用乘的肯定拆不开，只能用加哈希了。每次 \(x\) 加一的时候全局哈希值加上 \(\sum p_i\) 即可。
#include <bits/stdc++.h>
const int p = 998244353;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 5;
struct {
int l, r, s;
long long u;
} t[maxn << 2];
long long base[maxn];
#define lt (p << 1)
#define rt (lt | 1)
void pushup(int p) {
t[p].u = (t[lt].u * base[t[rt].s] % mod + t[rt].u) % mod;
return;
}
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r)
return;
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
void add(int p, int x, int v) {
t[p].s += (v >= 0 ? 1 : -1);
if (t[p].l == t[p].r) {
t[p].u += v;
return;
}
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid)
add(lt, x, v);
else
add(rt, x, v);
pushup(p);
return;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<int> a(n + 1), b(m + 1), pos(m + 1);
base[0] = 1;
long long s = 1;
for (int i = 1; i <= m; ++i) {
base[i] = base[i - 1] * p % mod;
if (i < n)
(s += base[i]) %= mod;
}
long long now = 0;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
now = (now * p % mod + a[i]) % mod;
}
for (int i = 1; i <= m; ++i)
std::cin >> b[i], pos[b[i]] = i;
int res = 0;
bld(1, 1, m);
for (int x = 0; x <= m - n; ++x) {
for (static int l = 1; l < 1 + x; add(1, pos[l], -l), ++l);
// printf("add %d: %d\n", pos[l], -l);
for (static int r = 1; r <= n + x; add(1, pos[r], r), ++r);
// printf("add %d: %d\n", pos[r], r);
(res += (now == t[1].u));
// printf("x = %d, now = %lld, t[1].u = %lld\n", x, now, t[1].u);
(now += s) %= mod;
}
std::cout << res << '\n';
return 0;
}B. k-substrings
http://222.180.160.110:61235/contest/5653/problem/2
我们可以发现这 \(\left\lceil\dfrac n2\right\rceil\) 个串都有共同中点，而不管其位于元素还是元素间的空隙，两边的 border 都应关于其对称。啥叫奇 border 呢，就是每个 border 都能取到元素上的中点，也就是说这俩中点是关于全串中点对称的。
我们枚举这 \(\left\lfloor\dfrac n2\right\rfloor\) 对可能的 border 中点，分别二分 border 长度。假设最后该对中点最长合法 border 为 \([l_1,r_1]\) 与 \([l_2,r_2]\)，用 \(r_1-l_1+1-2\times k\) 更新 \(l_1+k\) 处的答案即可。
#include <bits/stdc++.h>
const int p = 131;
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<char> a(n + 1);
std::vector<int> res(n + 1, -1);
std::vector<long long> h(n + 1), base(n + 1);
base[0] = 1;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
h[i] = (h[i - 1] * p + a[i]) % mod;
base[i] = base[i - 1] * p % mod;
}
auto geth = [&](int l, int r) {
return (h[r] + mod - h[l - 1] * base[r - l + 1] % mod) % mod;
};
for (int l = n / 2, r = (n + 1) / 2 + 1; r <= n; --l, ++r)
if (a[l] == a[r]) {
int t = 0;
for (int ll = 1, rr = l, mid; ll <= rr; ) {
mid = (ll + rr) >> 1;
if (geth(l - mid + 1, l + mid - 1) == geth(r - mid + 1, r + mid - 1))
t = mid, ll = mid + 1;
else
rr = mid - 1;
}
res[l - t + 1] = std::max(res[l - t + 1], 2 * t - 1);
}
for (int i = 1; i <= (n + 1) / 2; ++i) {
res[i] = std::max(res[i - 1] - 2, res[i]);
std::cout << res[i] << ' ';
}
std::cout << '\n';
return 0;
}C. Kefa and Watch
http://222.180.160.110:61235/contest/5653/problem/3
一个挺常用的 trick 是，\(S_{l\sim r}\) 存在长度为 \(d\) 的循环节 \(\iff S_{l\sim (r-d)}=S_{(l+d+)\sim r}\)。而题目要求为混循环节，刚好也可以用这个方法判定。线段树随便维护一下哈希就行。assign 操作就是将长度为 \(len\) 的区间哈希值更改为 \(t\times \sum_{i=0}^{len-1}p^i\)。
#include <bits/stdc++.h>
const int p = 131;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
struct {
int l, r, d;
long long u;
} t[maxn << 2];
int a[maxn];
long long base[maxn], s[maxn];
#define lt (p << 1)
#define rt (lt | 1)
void pushup(int p) {
t[p].u = (t[lt].u * base[t[rt].r - t[rt].l + 1] % mod + t[rt].u) % mod;
return;
}
void pushdown(int p) {
if (~t[p].d) {
t[lt].d = t[rt].d = t[p].d;
t[lt].u = t[p].d * s[t[lt].r - t[lt].l] % mod;
t[rt].u = t[p].d * s[t[rt].r - t[rt].l] % mod;
t[p].d = -1;
}
return;
}
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r, t[p].d = -1;
if (l == r) {
t[p].u = a[l];
return;
}
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
pushup(p);
return;
}
void ass(int p, int l, int r, int v) {
if (l <= t[p].l && t[p].r <= r) {
t[p].d = v;
t[p].u = v * s[t[p].r - t[p].l] % mod;
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
ass(lt, l, r, v);
if (r > mid)
ass(rt, l, r, v);
pushup(p);
return;
}
long long ask(int p, int l, int r) {
// printf("p = %d, u = %lld, [%d, %d] of [%d, %d]\n", p, t[p].u, t[p].l, t[p].r, l, r);
if (l <= t[p].l && t[p].r <= r)
return t[p].u;
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (r <= mid)
return ask(lt, l, r);
if (l > mid)
return ask(rt, l, r);
return (ask(lt, l, r) * base[std::min(r, t[p].r) - mid] % mod + ask(rt, l, r)) % mod;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m, k;
std::cin >> n >> m >> k;
base[0] = s[0] = 1;
for (int i = 1; i <= n; ++i) {
char t;
std::cin >> t;
a[i] = t - '0';
base[i] = base[i - 1] * p % mod;
s[i] = (s[i - 1] + base[i]) % mod;
}
bld(1, 1, n);
for (int q = m + k; q--; ) {
int op;
std::cin >> op;
if (op == 1) {
int l, r, t;
std::cin >> l >> r >> t;
ass(1, l, r, t);
}
else {
int l, r, d;
std::cin >> l >> r >> d;
// if (d != r - l + 1)
// printf("%lld / %lld\n", ask(1, l, r - d), ask(1, l + d, r));
std::cout << ((d == r - l + 1 || ask(1, l, r - d) == ask(1, l + d, r)) ? "YES" : "NO") << '\n';
}
}
return 0;
}D. Misha and LCP on Tree
http://222.180.160.110:61235/contest/5653/problem/4
一个很显然的做法是，我们二分一个长度，然后在 \(a\to fa\) 上正哈希，\(b\to fa\) 上反哈希，\(O(1)\) check。
笑话：本来想用倍增求 \(a\to fa\) 和 \(b\to fa\) 的哈希（当然双 \(\log\) 肯定是会被卡飞的），后来发现哈希具有可减性，我们又只需求一条链上的哈希值，直接减掉就行。
还有一个点就是 \(O(1)\) 求 \(k\) 级祖先，有长剖预处理的做法。具体做法。
#include <bits/stdc++.h>
const int p = 131;
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<int> to(n + 1);
std::vector<char> a(n + 1);
std::vector<std::vector<int> > g(n + 1);
std::vector<long long> base(n + 1), inv(n + 1);
auto qkp = [](long long x, int y) {
long long res = 1;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
base[0] = inv[0] = 1;
for (int i = 1, mx = 0; i <= n; ++i) {
std::cin >> a[i];
base[i] = base[i - 1] * p % mod;
inv[i] = qkp(base[i], mod - 2);
if (i >= (1 << mx) * 2)
++mx;
to[i] = mx;
}
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
std::vector<long long> h1(n + 1), h2(n + 1);
std::vector<std::array<int, 21> > fa(n + 1);
std::vector<int> h(n + 1, 1), son(n + 1), dep(n + 1);
h[0] = 0;
std::function<void(int)> DFS = [&](int x) {
h1[x] = (h1[fa[x][0]] * p % mod + a[x]) % mod;
h2[x] = (h2[fa[x][0]] + a[x] * base[dep[x] - 1]) % mod;
for (auto i : g[x])
if (i != fa[x][0]) {
fa[i][0] = x;
for (int j = 1; j <= 20; ++j)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
dep[i] = dep[x] + 1;
DFS(i);
if (h[i] >= h[son[x]])
son[x] = i, h[x] = h[i] + 1;
}
return;
};
dep[1] = 1, DFS(1);
std::vector<int> top(n + 1), id(n + 1);
std::vector<std::vector<int> > anc(n + 1), des(n + 1, std::vector<int> (1));
std::function<void(int, int)> DFS1 = [&](int x, int toq) {
top[x] = toq;
if (son[x])
DFS1(son[x], toq);
for (auto i : g[x])
if (i != fa[x][0] && i != son[x])
DFS1(i, i);
des[toq].push_back(x);
id[x] = (int)des[toq].size() - 1;
if (x == toq) {
anc[x].push_back(x);
for (int j = 1, now = x; j <= id[x]; ++j, now = fa[now][0])
anc[x].push_back(fa[now][0]);
}
return;
};
DFS1(1, 1);
auto getLCA = [&](int x, int y) {
if (dep[x] < dep[y])
std::swap(x, y);
for (int i = 20; ~i; --i)
if (dep[fa[x][i]] >= dep[y])
x = fa[x][i];
if (x == y)
return x;
for (int i = 20; ~i; --i)
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
};
auto ask = [&](int x, int k) {
assert(dep[x] - 1 >= k);
int x1 = x;
if (!k)
return x;
x = fa[x][to[k]];
if (dep[x] - dep[top[x]] >= k - (1 << to[k]))
return des[top[x]][id[x] + k - (1 << to[k])];
return anc[top[x]][k - (1 << to[k]) - (dep[x] - dep[top[x]])];
};
auto dis = [&](int x, int y, int fa) {
return dep[x] + dep[y] - 2 * dep[fa];
};
auto gethash = [&](int x, int y, int f, int k) {
if (!k)
return 0ll;
if (k <= dep[x] - dep[f] + 1) {
f = ask(x, k - 1);
return (h2[x] + mod - h2[fa[f][0]]) % mod * inv[dep[f] - 1] % mod;
}
long long h = (h2[x] + mod - h2[fa[f][0]]) % mod * inv[dep[f] - 1] % mod;
k -= (dep[x] - dep[f] + 1);
y = ask(y, (dep[y] - dep[f]) - k);
h = (h * base[dep[y] - dep[f]] % mod + (h1[y] + mod - h1[f] * base[dep[y] - dep[f]] % mod) % mod) % mod;
return h;
};
int m;
std::cin >> m;
for (int x, y, a, b; m--; ) {
std::cin >> x >> y >> a >> b;
int fa1 = getLCA(x, y), fa2 = getLCA(a, b), res = 0;
for (int l = 0, r = std::min(dis(x, y, fa1), dis(a, b, fa2)) + 1, mid; l <= r; ) {
mid = (l + r) >> 1;
if (gethash(x, y, fa1, mid) == gethash(a, b, fa2, mid))
res = mid, l = mid + 1;
else
r = mid - 1;
}
std::cout << res << '\n';
}
return 0;
}A. Song of the Sirens
http://222.180.160.110:61235/contest/5658/problem/1
笑话：是 \(s_it_is_i\) 而不是 \(s_its_i\)。
我们发现 \(s_0\) 很短，所以直接枚举起始位置把 \(s_0\) 和匹配串大力匹配，把空位挖出来组成新的匹配串再考虑 \(t\) 的问题（因为所有 \(s_i\) 最开头都有一个完整的 \(s_0\)，所以可以随便选断点）。
我们知道 \(t\) 的下标是一个自底向上从 \(1\) 到 \(n\) 的满二叉树的中序遍历，其中 \(t_1\) 间隔一位出现；于是我们仿照对 \(s\) 的处理方式，再把 \(t_1\) 挖掉。注意到此时 \(t_2\) 又成为二叉树最底层，间隔一位出现，这就变成了一个 \(\mathcal O(n\log n)\) 递归的问题。
至于答案，当 \(t\) 被删空时，假设删掉的最后一个元素为 \(t_p\)，\(t\) 的出现次数即为二叉树中 \(p\) 层点数，为 \(2^{k-p}\)。
有一个细节，就是如果当前删到 \(i\) 了，\(t\) 的长度只剩 \(1\)，就会有一个很尴尬的问题——这个元素不一定就是 \(t_i\)，而应该是 \(\{j \mid j\ge i\land t_j=t_i\}\)。统计 \(t_{i\sim k}\) 中值为 \(t_i\) 的元素个数（前缀和），乘上对应的层数即可。这个可以用一点小技巧搞定，前缀和时忽略 \(k\) 乘上 \(k=n\) 时的系数，统计答案时乘上 \(2^{n-k}\) 即可。
不是，那我缺的哈希这块谁来补啊？？？
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen("sirens1.in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, q, m;
std::string s;
std::cin >> n >> q >> s;
s = '\0' + s, m = (int)s.length() - 1;
std::vector<char> t(n + 1);
std::vector<long long> base(n + 1), inv(n + 1);
std::vector<std::array<long long, 26> > a(n + 1);
auto qkp = [](long long x, int y) {
long long res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
base[0] = 1ll, inv[0] = 1ll, inv[1] = qkp(2, mod - 2);
for (int i = 1; i <= n; ++i) {
std::cin >> t[i];
base[i] = base[i - 1] * 2 % mod;
if (i != 1)
inv[i] = inv[i - 1] * inv[1] % mod;
}
for (int i = 1; i <= n; ++i)
a[i] = a[i - 1], (a[i][t[i] - 'a'] += base[n - i]) %= mod;
for (int k; q--; ) {
std::string p;
std::cin >> k >> p;
p = '\0' + p;
long long res = 0;
int l = (int)p.length() - 1;
std::vector<char> u;
std::function<void(int, std::vector<char> &)> calc = [&](int x, std::vector<char> &p) {
int m = (int)p.size() - 1;
if (m == 0) {
// puts("# 45");
// printf("0, += %lld\n", base[k - x + 1]);
(res += base[k - x + 1]) %= mod;
return;
}
if (x > k)
return;
if (m == 1) {
// puts("# 50");
// printf("1, += %lld(%lld)\n", (a[k][p[1] - 'a'] + mod - a[x - 1][p[1] - 'a']) % mod * inv[n - k] % mod, inv[n - k] % mod);
(res += (a[k][p[1] - 'a'] + mod - a[x - 1][p[1] - 'a']) % mod * inv[n - k] % mod) %= mod;
return;
}
bool flag0 = 1, flag1 = 1;
std::vector<char> t0(1), t1(1);
for (int i = 1; i <= m; ++i)
if (!(i & 1)) {
if (flag0)
t0.push_back(p[i]);
flag1 &= (p[i] == t[x]);
}
else {
if (flag1)
t1.push_back(p[i]);
flag0 &= (p[i] == t[x]);
}
if (flag0)
calc(x + 1, t0);
if (flag1)
calc(x + 1, t1);
return;
};
for (int i = 1; i <= m + 1; ++i) {
std::vector<char>(1).swap(u);
for (int j = i, now = 1; now <= l; ++now) {
if (j == m + 1)
j = 1, u.push_back(p[now]);
else if (p[now] != s[j])
goto nosol;
else
++j;
}
// printf("u: ");
// for (int i = 1; i < (int)u.size(); ++i)
// std::cout << u[i];
// puts("");
calc(1, u);
nosol: ;
}
std::cout << res << '\n';
}
return 0;
}B. Prefix of Suffixes
http://222.180.160.110:61235/contest/5658/problem/2
还是太科幻了。哦哦 border 我的 border。
法一
考虑每次增量，若加入 \(S_i\) 后有 \(z_j\) 的值增加 \(1\)，那么这对 \((i, j)\) 就会贡献 \(A_j\cdot B_i\) 的增量；反之，\(z_j\) 在以后也不会增加。
我们维护当前没有确定下来的所有 \(z_j\)，对于每个 \(i\) 暴力 check \(z_j\)
是否确定并更新答案，因为数据比较弱，在 CF
神机上跑得飞快 
但是 QOJ 上死活过不了 
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
long long res = 0, s = 0;
std::cin >> n;
std::vector<int> now;
std::vector<int> a(n + 1), b(n + 1), t(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> t[i] >> a[i] >> b[i];
t[i] = (res + t[i]) % n;
if (t[i] == t[1])
s += b[i], now.push_back(i);
std::vector<int> g(std::move(now));
for (auto j : g)
if (t[i] == t[i - j + 1])
now.push_back(j);
else
s -= b[j];
res += a[i] * s;
std::cout << res << '\n';
}
return 0;
}法二
依然考虑增量。\(z_j\) 增加 \(\iff S_{j\to i}\) 为 \(S_{1\sim i}\) 的一个 border。考虑对于每一个 \(S_i\)，border 的组成。
- 若 \(S_1=S_i\)，那么将会新增一个长度为 \(1\) 的 border。
- 对于在 \(i-1\) 处合法的 border \(S_{j\sim i-1}\)，若 \(S_i=S_{i-j+1}\)，则该 border 仍合法；否则非法。
我们的法一其实相当于是暴力 check 了所有合法 border 是否仍然合法，但这显然最坏是 \(O(n^2)\) 的。我们考虑从 border 角度优化一下。
我们发现，比如说 \(\texttt{abababa + b}\)，我们会进行很多次不必要的 check，当然这个时候我们会本能大力跳 fail，但是这里有一个 border 的等差数列性质，若 \(x+1\) 与 \(i\) 能够匹配，那么与 \(x\) 同属一个等差数列的所有 \(x'+1\) 都应和 \(i\) 匹配。
对于正在 check 的 \(x\)，如果 check 成功则跳到上一条链的链尾；否则跳到链头。总的复杂度是 \(O(n\log n)\) 的。找一下和每个 \(i\) 匹配不了的第一个链头，甚至可以因为某些我太菜了所以不知道的不明原因整到线性。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
long long res = 0, s = 0;
std::cin >> n;
std::vector<int> a(n + 1), b(n + 1), t(n + 1), ne(n + 1), to(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> t[i] >> a[i] >> b[i];
t[i] = (res + t[i]) % n;
if (i == 1)
s += b[i], res = (long long)a[i] * b[i];
else {
int j = ne[i - 1];
for (; j && t[j + 1] != t[i]; j = ne[j]);
if (t[j + 1] == t[i])
++j;
ne[i] = j;
if (t[i] == t[1])
s += b[i];
to[i - 1] = (t[ne[i - 1] + 1] == t[i] ? to[ne[i - 1]] : ne[i - 1]);
for (int j = i - 1; j; )
if (t[j + 1] == t[i])
j = to[j];
else
for (int at = to[j]; j != at; s -= b[i - j], j = ne[j]);
res += a[i] * s;
}
std::cout << res << '\n';
}
return 0;
}C. Matching
http://222.180.160.110:61235/contest/5658/problem/3
我们发现，如果我们直接要 check 一段 \(a\) 和 \(p\)，感觉不太好整。
然后考虑这么一个问题，假如我们通过神秘方法让我们每次 check 的 \(a\)