2025.2.21 日校内模拟赛总结（AC自动机， 期望，倍增）

时间安排

将近两个半小时才过 $T1$，后面花一个半小时过了 $T2$，最后半个小时写不出 $T3$ 暴力没有获得分数。

反思：

1. $T1$ 这种题要敢于去猜结论打表，由于没有直接猜结论做了很长时间。但是猜到结论后就比较好做。
2. 做 $T2$ 时节奏还是不错的，先写了暴力，然后发现暴力复杂度比较玄学。后面又想到了正解。

题解

点我

题意：
给你 $n$ 个长度为 $m$ 的字符串 $T_1,T_2,...,T_n$，保证仅由前 $k$ 个小写字母构成。
定义函数 $f(S,T,p)$，其中 $S$ 为一个字符串， $T$ 为上述的 $n$ 个字符号串， $p$ 为一个长度为 $k$ 的概率数组。每次操作会在 $S$ 后面以 $p_i$ 的概率接上第 $i$ 种字符，如果某一时刻 存在某个$i$ 满足 $T_i$ 是 $S$ 的子串则停止操作。$f(S,T,p)$ 等于 停止操作时 $S$ 的期望长度。
开始时给你一个字符串 $R$，和一个长度为 $k$ 的数组 $p$。你需要按顺序执行 $Q$ 次操作，操作分两种：
1 l c：修改操作，将 $R$ 的后 $l$ 个字符替换成 $c$。
2 l：查询操作，查询 $R$ 长度为 $l$ 的前缀的函数值 $f(R[1,...,l],T,p)$

数据规模：
$1\le n\le 100$， $n\times m\le 10^4$，$1\le k\le 26$， $1\le |R|\le 10^4$， $1\le Q\le 10^5$

分析：
发现 $T$ 和 $p$ 是不会变的，多模式串匹配显然考虑 $AC$ 自动机。那么可以把原问题分解成两个问题：
1.在 $AC$ 自动机上某个节点以一定概率随机游走，求走到叶子的期望步数。
2. 支持修改字符串后缀，快速求出一个前缀字符串在 $AC$ 自动机上的对应节点。
我们一个一个看。

对于第一个问题：
首先由于所有 $T_i$ 长度相等，因此对应的终止节点就是所有的叶子。将每个节点的期望值看作一个变量，对于节点 $p$，可以列出以下方程：
若 $p$ 为非叶子：$E_p=1+\sum _c{p}_c\times E_{t{r}_{p,c}}$
若 $p$ 为叶子： $E_p=0$

暴力高消的复杂度为 $O((n\times m{)}^3)$，显然无法通过。
正解感觉很神奇：我们可以用 $n$ 个变量表示所有节点的期望值，然后再利用 $n$ 个叶子的期望为 $0$ 得到 $n$ 个方程从而在 $O(n^3+n^{2}m)$ 的复杂度得到所有节点的期望。
具体做法是这样：由于 $trie$ 树上最多有 $n$ 个叶子，因此我们一定能自上到下将树划分成若干条不交链。设 $i$ 号点在链上的后继为 $nx{t}_i$，对应的边为 $c$。考虑按照深度 $bfs$ 以此确定每个点的期望如何被变量表示。假设当前队头节点为 $u$，深度为 $t$，那么可以认为前 $t$ 层节点的期望都已经被表示过了。枚举 $u$ 的出边 $t{r}_{u,i}$，分两种情况讨论：

1. $t{r}_{u,i}\ne nx{t}_u$。若 $t{r}_{u,i}$ 的深度小于等于 $u$，那么它的期望值一定被表示过了。若 $t{r}_{u,i}$ 的深度大于 $u$，那么他是一条链的链头，新开一个变量表示它的期望即可。
2. $t{r}_{u,i}=nx{t}_u$。 那么可以得到 $E_{nx{t}_u}=\frac{E_u-\sum _{v\ne c}{p}_v\times E_{t{r}_{u,v}}-1}{p_c}$ 。

不难发现每次只会在一条链的链头新开一个变量，因此只会开 $n$ 个变量。然后利用 $n$ 个叶子的期望为 $0$ 就可以把所有期望解出来。

第二个问题：
每次后缀推平，容易想到 颜色段均摊，因此可以开一个 栈 来维护相同颜色段。
每个颜色段需要处理出一个二元组信息 $(x,f)$ 表示把这个段前面的所有段都走过后当前的节点为 $x$，$f$ 表示是否已经经过叶子。然后可以对 $trie$ 树每个节点 $p$ 维护一个倍增数组 $h_{p,c,i}$ 表示从 $p$ 开始沿着 $c$ 边连续走 $2^i$ 步会到那个节点，以及是否经过叶子。每次询问就二分出在哪一段然后跑一遍倍增即可。
对于修改，暴力弹栈加栈复杂度就是对的。

总复杂度 $O(n^3+n^{2}m+Q\times \log |R|)$。

CODE：

// 分为两部分：
// 第一部分：求出AC自动机上每个点的期望值
// 这一部分的难点在于如何减少未知变量的个数
// 链剖分之
// 第二部分：如何维护快速查询一个前缀在AC自动机上的位置以及是否经过叶子
// 开一个栈维护连续颜色段倍增查询即可
#include<bits/stdc++.h>
#define MP make_pair
#define pb emplace_back
using namespace std;
typedef long long LL;
typedef pair< int, int > PII;
const LL mod = 1e9 + 7;
const int N = 105;
const int M = 1e4 + 10;
PII h[15][N * N][26];
int n, m, K, q;
int fail[N * N], tr[N * N][26], tot = 1;
int nxt[N * N];
char str[M];
bool leaf[N * N];
LL p[N], invp[N], inv, E[N * N];
void ins(char *str) {int len = strlen(str + 1); int p = 1;for(int i = 1; i <= len; i ++ ) {if(!tr[p][str[i] - 'a']) tr[p][str[i] - 'a'] = ++ tot;p = tr[p][str[i] - 'a'];}leaf[p] = 1; // 叶子
}
void dfs(int p, int lst) {bool f = 1;for(int i = 0; i < K; i ++ ) {if(tr[p][i]) {if(f) nxt[p] = tr[p][i], f = 0, dfs(tr[p][i], p);else dfs(tr[p][i], 0);}}
}
void build_AC() {queue< int > q; fail[1] = 1;for(int i = 0; i < K; i ++ ) {if(tr[1][i]) q.push(tr[1][i]), fail[tr[1][i]] = 1;else tr[1][i] = 1;}while(!q.empty()) {int u = q.front(); q.pop();for(int i = 0; i < K; i ++ ) {if(tr[u][i]) fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);else tr[u][i] = tr[fail[u]][i];}}
}
namespace expection {int r; // 表示当前的变量数LL f[N * N][N]; // 每个点对每个变量的系数  0 为常数LL g[N], val[N]; // val[i] 表示每个变量的真实值bool vis[N * N];inline LL Pow(LL x, LL y) {LL res = 1LL, k = x;while(y) {if(y & 1) res = res * k % mod;y >>= 1;k = k * k % mod;}return res;}struct Guess {int h;LL a[N][N]; void init() {for(int i = 1; i <= tot; i ++ ) {if(leaf[i]) {h ++;for(int j = 1; j <= r; j ++ ) a[h][j] = f[i][j];a[h][r + 1] = (mod - f[i][0]) % mod;}}}void calc() {for(int i = 1; i <= r; i ++ ) { int idx;for(int j = i; j <= h; j ++ ) if(a[j][i]) {idx = j; break;}for(int j = 1; j <= r + 1; j ++ ) swap(a[i][j], a[idx][j]);LL inv = Pow(a[i][i], mod - 2LL);for(int j = 1; j <= r + 1; j ++ ) a[i][j] = a[i][j] * inv % mod;for(int j = 1; j <= h; j ++ ) {if(j == i) continue;LL p = a[j][i];for(int k = 1; k <= r + 1; k ++ ) a[j][k] = (a[j][k] - a[i][k] * p % mod + mod) % mod;}}for(int j = 1; j <= r; j ++ ) val[j] = a[j][r + 1];}} G;void bfs(int s) {r ++; f[s][r] = 1;queue< int > q; q.push(s); vis[s] = 1;while(!q.empty()) {int u = q.front(); q.pop(); // 假设 u 已经能表示出来了if(!nxt[u]) continue;for(int j = 0; j <= r; j ++ ) g[j] = f[u][j]; // 系数清空LL Inv;for(int i = 0; i < K; i ++ ) {if(!tr[u][i]) continue;if(tr[u][i] == nxt[u]) {Inv = invp[i]; continue;} // 在一个链上else if(!vis[tr[u][i]]) { // 没标记vis[tr[u][i]] = 1;r ++; f[tr[u][i]][r] = 1;q.push(tr[u][i]);}for(int j = 0; j <= r; j ++ ) g[j] = (g[j] - p[i] * f[tr[u][i]][j] % mod + mod) % mod;}g[0] = (g[0] - 1 + mod) % mod;for(int j = 0; j <= r; j ++ ) f[nxt[u]][j] = g[j] * Inv % mod;q.push(nxt[u]); vis[nxt[u]] = 1;}}void get() {for(int i = 0; i < K; i ++ ) inv = (inv + p[i]) % mod;inv = Pow(inv, mod - 2LL);for(int i = 0; i < K; i ++ ) p[i] = p[i] * inv % mod;for(int i = 0; i < K; i ++ ) invp[i] = Pow(p[i], mod - 2LL);bfs(1);G.init(); G.calc(); val[0] = 1;for(int i = 1; i <= tot; i ++ ) {LL res = 0;for(int j = 0; j <= r; j ++ ) res = (res + f[i][j] * val[j] % mod) % mod;E[i] = res;}}
}
struct seg {int l, r, c; // 起点PII p; // 起点，是否经过叶子
};
int top;
seg stk[M];
PII jump(PII s, int k, int c) {int x = s.first, f = s.second;for(int i = 14; i >= 0; i -- ) {if(k >> i & 1) f |= h[i][x][c].second, x = h[i][x][c].first;}return MP(x, f);
}
void add(int l, int r, int c) {PII p = stk[top].p; int lc = stk[top].c;p = jump(p, stk[top].r - stk[top].l + 1, lc);stk[++ top] = (seg) {l, r, c, p};
}
void del(int l) {if(l <= stk[top].l) top --;else stk[top].r = l - 1;
}
LL ask(int x) {int l = 1, r = top, mid, res;while(l <= r) {mid = (l + r >> 1);if(stk[mid].r >= x) res = mid, r = mid - 1;else l = mid + 1;}PII p = jump(stk[res].p, x - stk[res].l + 1, stk[res].c);return p.second == 1 ? 0LL : E[p.first];
}
int main() {freopen("string.in", "r", stdin);freopen("string.out", "w", stdout);scanf("%d%d%d", &n, &m, &K);for(int i = 0; i < K; i ++ ) {scanf("%lld", &p[i]);}for(int i = 1; i <= n; i ++ ) {scanf("%s", str + 1);ins(str);}dfs(1, 0); // 划分出 n 条链build_AC();for(int i = 1; i <= tot; i ++ ) {for(int j = 0; j < K; j ++ ) {h[0][i][j].first = tr[i][j];h[0][i][j].second |= leaf[tr[i][j]];}}for(int i = 1; i <= 14; i ++ ) {for(int j = 1; j <= tot; j ++ ) {for(int k = 0; k < K; k ++ ) {h[i][j][k].first = h[i - 1][h[i - 1][j][k].first][k].first;h[i][j][k].second = h[i - 1][j][k].second | h[i - 1][h[i - 1][j][k].first][k].second;}}}expection::get();scanf("%s", str + 1); int R = strlen(str + 1);stk[++ top] = (seg) {0, -1, 0, MP(1, 0)};for(int i = 1; i <= R; ) {int j = i;while(j <= R && str[j] == str[i]) j ++;add(i, j - 1, str[i] - 'a');i = j;}for(int i = 1; i <= R; i ++ ) {printf("%lld\n", i + ask(i));}scanf("%d", &q);for(int i = 1; i <= q; i ++ ) {int opt, l; char c;scanf("%d%d", &opt, &l); if(opt == 1) scanf("\n%c", &c);if(opt == 1) {l = R - l + 1;while(stk[top].r >= l) del(l);add(l, R, c - 'a');}else printf("%lld\n", l + ask(l));}return 0;
}