有一种人生中最后一篇杂题的感觉，尽量还有下一篇吧
发现自己写的主题虽然 Linux 下看起来非常美观，但是 Windows 下非常丑陋（微软雅黑我喜欢你），希望还有机会修掉这个 bug！
“上一届的女生也是抱着‘感觉自己实在算不上强，只能寄希望于下一个年级的女生因为还没到高二没有警惕了！’的心情上考场的吗？”
唉！妄想症又在骚扰我了！
“跳ねた電気で脳裏を満たして”，用神经元的电信号填满脑袋吧…… 空を満たして完播率 100%…… 果然是这样吗，听到对味的歌之后接下来若干天都舍不得跳
只有 Dopping Dance By STEAKA & White Mind By Blue 直至目前完播率 100%……
现在就怀念可以轻松打出直角引号的 Linux 了。
怎么忘了 AC 自动机可以干啥了，明明昨天还记得
越是这种时候越是慌张。耳机里播着林田匠的 DOEs，或许这就是 John Doe 的写照吧。
好在我还有自己的博客。？怎么看不懂。？怎么博客里也没写可以干啥。
小雷！lhy 是很好的 lhy。大的那个 lhy，不是小的那个 lhy……
那这么说 lhy 岂不是应该叫大雷。大雷一律 0 分（哈气）
你怎么摘我耳机啊，旮旯给木里不是这样的！无妨，摘了耳机我也能跳ねた電気で脳裏を満たして。
A - 销售基因链 / Selling RNA Strands
https://www.luogu.com.cn/problem/P9196
-
很容易想到 ACAM 的做法，显然此处每次询问的后缀是模式串，故离线下来建 ACAM
记录每个初始串对于每个模式串的匹配结果，DSU on tree 即可单 log
-
接下来在 Trie 上跑前缀统计，更简单的可以在 DSU 时就统计一下。复杂度 \(O(n\log n)\)。但是糖丸了！
-
正确的 AC 自动机做法是，考虑到前后缀是分开的很难受，把询问的
P和Q写成Q#P加入自动机，再用S#S匹配即可复杂度线性而且非常好实现。糖丸了！
#include <bits/stdc++.h>
const int maxn = 5e6 + 5;
int T[maxn][5], fail[maxn], cnt[maxn], deg[maxn], tot;
int tab(char t) {switch (t) {case 'A':return 0;case 'C':return 1;case 'G':return 2;case 'U':return 3;}return 4;
}
int ins(std::string &s) {int p = 0;for (auto i : s) {if (!T[p][tab(i)])T[p][tab(i)] = ++tot;p = T[p][tab(i)];}return p;
}
int main() {
#ifdef ONLINE_JUDGEstd::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);
#elsestd::freopen(".in", "r", stdin);std::freopen(".out", "w", stdout);auto stime = std::chrono::steady_clock::now();
#endifint n, m;std::cin >> n >> m;std::vector<std::string> s(n + 1);for (int i = 1; i <= n; ++i) {std::cin >> s[i];s[i] = s[i] + '#' + s[i];}std::vector<int> tail(m + 1);for (int i = 1; i <= m; ++i) {std::string p, q;std::cin >> p >> q, p = q + '#' + p;tail[i] = ins(p);}{std::queue<int> q;for (int i = 0; i < 5; ++i)if (T[0][i])q.push(T[0][i]);for (; !q.empty(); ) {int u = q.front();q.pop();for (int i = 0; i < 5; ++i)if (T[u][i]) {int v = T[u][i];fail[v] = T[fail[u]][i];++deg[T[fail[u]][i]];q.push(v);}elseT[u][i] = T[fail[u]][i];}}for (int i = 1; i <= n; ++i) {int p = 0;for (auto j : s[i]) {p = T[p][tab(j)];++cnt[p];}}{std::queue<int> q;for (int i = 0; i <= tot; ++i)if (!deg[i])q.push(i);for (; !q.empty(); ) {int u = q.front();q.pop(), cnt[fail[u]] += cnt[u];if (!--deg[fail[u]])q.push(fail[u]);}}for (int i = 1; i <= m; ++i)std::cout << cnt[tail[i]] << '\n';
#ifndef ONLINE_JUDGEstd::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double>(std::chrono::steady_clock::now() - stime).count() << "s\n";
#endifreturn 0;
}
Balance
https://www.luogu.com.cn/problem/P9731
给定 \(n\times m\) 的二维数组 \(a_{i,j}\)，且 \(1\le a_{i,j}\le k\)。你需要重排每一行，使得：
- 对于每个 \(1\le c\le k\)，都能找到一个 \(v_c\)，使得每一列中，\(c\) 的出现次数要么为 \(v_c\)，要么为 \(v_c+1\)。
输出任意合法重排后数组。
\(1\le n,m,k\le 10^5\)，\(n\times m\le 5\times 10^5\)，且 \(m\) 为 \(2\) 的次幂。