ACM-ICPC 南昌网络赛F题 Megumi With String
题目描述
给一个长度为\(l\)的字符串\(S\)，和关于\(x\)的\(k\)次多项式\(G[x]\).当一个字符串\(str\)是S的子串时，定义\(str\)的\(value\)值为\(G[length(str)]\)，否则\(value=0\)。一个字符串的\(power\)值定义为其所有子串的\(value\)之和。每次向\(S\)末尾添加一个字符，重复\(m\)次。求每次添加字符后，一个长度为\(n\)的随机串\(T\)的\(power\)期望值。每个测试点\(Q\)组数据
- 出现在不同位置的相同串视为\(T\)的不同子串
- 多项式的次数不大于\(50\)
\(\sum l,\sum m,\sum k\leq 3\times10^5\)
题解
- 由于串是随机的，所以不适合以特定串为研究对象。因此考虑指定长度的子串的贡献。长度为\(i\)的串的贡献正比于\(S\)中长度为\(i\)的本质不同的子串个数。由于要在线添加字符，所以使用后缀自动机维护以上信息。
使用后缀自动机维护本质不同的子串个数有两种方法：
- 由于从源点沿转移边到达的点所经过的路径都是一个子串，所以\(f[i]=\sum _{i\rightarrow j}(f[j] + 1)\)，\(f[i]\)表示从i出发的路径个数，答案为\(f[\empty]\)
- SAM上每一个结点都代表一个等价类，该节点包含了长度为\((longest(fa[i]),longest(i)]\)的子串，而每一个节点包含的子串都不相同。
显然，用方法2可以更方便地在插入字符时就更新\((longest(fa[i]),longest(i)]\)的子串个数变化。
\(S\)的最终长度为\(l+m\),其中长度大于\(n\)的子串不会产生贡献。所以我们处理的子串长度范围是\([1,min(l+m,n)]\)，设\(N=min(l+m,n)\)
\(T\)的总个数为\(26^n\)
长度为\(i\)的子串出现的总次数为\((n-i+1)\cdot 26^{n-i+1}\)（出现在不同位置*周围不同字符）。所以长度为\(i\)的子串对\(power\)的贡献为\(cnt_i\cdot (n-i+1)\cdot 26^{n-i+1}\cdot G[i]\)
\(cnt_i\)表示\(S\)中长度为\(i\)本质不同的子串个数
则\(E_{power}(T)=\frac{1}{26^n}\sum_{i=1}^{min(l+m,n)}cnt_i\cdot (n-i+1)\cdot 26^{n-i+1}\cdot G[i]\)
令\(H[i]=(n-i+1)\cdot 26^{n-i+1}\cdot G[i]\)
- 由于\(H[i]\)只与\(i\)有关，因此可以预处理\(0\sim N\)的\(H\)值
因为每次只修改连续的区间，修改只有加一操作，而且求和的范围为固定的整个区间，因此可以预处理\(H[i]\)的前缀和，每次\(O(1)\)修改对应\(len\)区间的贡献，然后直接输出\(ans\)
if (fa.longest < n) ans = (0ll + ans + G[min(n, now.longest)] + P - G[fa.longest]) % P;
处理细节
- 处理多组数据注意后缀自动机的初始化
void init(int nn) {
memset(am[1].ch, 0, sizeof(am[0].ch));
las = cnt = 1;
n = nn;
}
//insert()
memset(am[cnt].ch, 0, sizeof(am[0].ch));
- 单个字符的读入——来自C语言的gank
让我误以为是读不进去，换了各种方法。最后发现其实是后缀自动机的构造函数写错才导致的TLE
把代码改的面目全非
for (i = 0; i < m; ++i) {
ch = getchar();
if (islower(ch))
AM.insert(ch);
else {
tt++;
i--;
if (tt > 4e5)
return 0;
continue;
}
printf("%d\n", (int)(1ll * ans * inv % P));
}
最后全部改回去了。
AC代码
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 2e5 + 1, P = 998244353, v26 = 729486258, sigma_size = 26; //v26=inv(26)
int G[maxn + 1], N, a[51], ans;
char S[100001];
int fexp(int x, int n) {
int ret = 1;
while (n) {
if (n & 1) ret = 1ll * ret * x % P;
x = 1ll * x * x % P;
n >>= 1;
}
return ret;
}
void getG(int len, int n, int K) {
int n26 = fexp(26, n);
G[0] = 0;
for (int i = 1; i <= len; ++i) {
int ans = 0, x = 1;
n26 = 1ll * n26 * v26 % P;
for (register int j = 0; j <= K; ++j) {
ans = (1ll * x * a[j] % P + ans) % P;
x = 1ll * x * i % P;
}
G[i] = ans;
G[i] = (1ll * G[i] * (n - i + 1) %P * n26 %P + G[i - 1]) % P;
}
return;
}
struct SAM {
struct Node {
int longest, fa;
int ch[sigma_size];
Node() {
memset(ch, 0, sizeof(ch));
longest = 0;
}
}am[maxn << 1];
int las = 1, cnt = 1, n;
void init(int nn) {
memset(am[1].ch, 0, sizeof(am[0].ch));
las = cnt = 1;
n = nn;
}
void insert(int c) {
int p = las, np = ++cnt;
memset(am[np].ch, 0, sizeof(am[0].ch));
las = np;
am[np].longest = am[p].longest + 1;
for (; p && !am[p].ch[c]; p = am[p].fa) am[p].ch[c] = np;
if (!p) am[np].fa = 1;
else {
int q = am[p].ch[c];
if (am[q].longest == am[p].longest + 1) am[np].fa = q;
else {
int nq = ++cnt;
am[nq] = am[q];
am[np].fa = nq;
am[nq].longest = am[p].longest + 1;
am[q].fa = nq;
for (; p && am[p].ch[c] == q; p = am[p].fa) am[p].ch[c] = nq;
}
}
if (am[am[np].fa].longest < n)
ans = (0ll + ans + G[min(n, am[np].longest)] + P - G[am[am[np].fa].longest]) % P;
}
}AM;
int main() {
int Q, l, m, K, i, n, inv;
char ch;
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
cin>>Q;
while (Q--) {
cin>>l>>K>>n>>m;
N = min(l + m, n);
ans = 0;
AM.init(n);
inv = fexp(fexp(26, n), P - 2);
cin>>S;
for (i = 0; i <= K; ++i)
cin>>a[i];
getG(N, n, K);
for (int j = 0; j < l; ++j) AM.insert(S[j]);
cout<<(1ll * ans * inv % P)<<endl;
for (i = 0; i < m; ++i) {
cin>>ch;
AM.insert(ch);
cout<<(1ll * ans * inv % P)<<endl;
}
}
return 0;
}