「牛客挑战赛31 E | Nowcoder 880E」密涅瓦的谜题

好久没更了 = =

现在看到什么题都感觉一脸不可做,水平太低了

题意

给出仅包含小写字母的长度为 \(n\) 的字符串 \(s\)

每次取出 \(s\) 的一个子串 \(t_i\)(可以为空),执行 \(m\) 次,顺次拼接成一个大字符串 \(t=t_1 t_2\dots t_m\),求可以得到多少种本质不同的 \(t\)

\(q\) 次询问,每次给出一个 \(m\)

\(n,q\le 10^5, m\le 10^{10}\)

做法

考虑 \(t\) 的一种唯一分解的方式(不会算重),每次取 \(t\) 最长的是 \(s\) 子串的前缀,作为这次选取的子串。由于更短的前缀也必然是一个子串,这种做法显然存在解且唯一的

一组 \(t_1 t_2 \dots t_m\) 合法当且仅当 \(\forall 1\le i<m\)\(t_i\) 加上 \(t_{i+1}\) 的第一个字符后不是 \(s\) 的子串

\(f_{i,j}\) 表示考虑了最后 \(i\) 次选取的子串,当前的第一个字符是 \(j\) 的方案数,只要保证新选取的子串加上 \(j\) 后不是 \(s\) 的子串即可转移

特殊的,\(j\) 可以为空字符,即第 \(m-i+1\) 次选取的是空串

\[f_{i,j}=\sum_k A_{k,j} \times f_{i-1,k}\]

其中 \(A\) 是系数矩阵,可以在 SAM 上 dp 得到

\(\sigma\) 表示字符集大小,复杂度 \(\mathcal O(n \sigma)\)

答案为

\[ \begin{bmatrix} 0 & \cdots & 0 & 1 \end{bmatrix} A^m \begin{bmatrix} 1 & \cdots & 1 & 1 \end{bmatrix} ^{\rm T} \]

考虑对 \(m\) 分块

答案转化为

\[ \begin{bmatrix} 0 & \cdots & 0 & 1 \end{bmatrix} A^{\left\lfloor \frac{m}{S} \right\rfloor \times S} \times A^{m \bmod S} \begin{bmatrix} 1 & \cdots & 1 & 1 \end{bmatrix} ^{\rm T} \]

左侧只有 \(\mathcal O(\frac{m}{S})\) 种取值,右侧只有 \(\mathcal O(S)\) 种取值。

\(S=\sqrt m\) 时取得总复杂度最小值 \(\mathcal O(\sqrt m \sigma^2 + (n+q) \sigma)\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>

using namespace std;
#define ll long long

inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig=false, c=read(); !isdigit(c); c=read()) {
if (c == '-') iosig=true;
if (c == -1) return;
}
for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
if (iosig) x=-x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
*ooh++=c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x==0) print('0');
else {
if (x<0) print('-'), x=-x;
for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
while(cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 100005, C = 26, K = C+1, P = 1000000007;
ll m;
int n, q, last, cnt, b[N], a[N<<1], fa[N<<1], len[N<<1], l[N][K], r[N][K], ch[N<<1][C], f[N<<1][K];
char s[N];
struct matrix{
int a[K][K];
inline matrix operator *(const matrix &r)const{
matrix ans;
memset(ans.a, 0, sizeof a);
for(int i=0; i<K; ++i) for(int k=0; k<K; ++k) for(int j=0; j<K; ++j)
ans.a[i][j]=(ans.a[i][j]+(ll)a[i][k]*r.a[k][j])%P;
return ans;
}
} A, B;
void extend(int c){
int p=last, np=++cnt;
last=cnt, len[np]=len[p]+1;
while(p && !ch[p][c]) ch[p][c]=np, p=fa[p];
if(!p) fa[np]=1;
else{
int q=ch[p][c];
if(len[q]==len[p]+1) fa[np]=q;
else{
int nq=++cnt;
len[nq]=len[p]+1, memcpy(ch[nq], ch[q], C<<2);
fa[nq]=fa[q], fa[q]=fa[np]=nq;
while(ch[p][c]==q) ch[p][c]=nq, p=fa[p];
}
}
}
inline matrix Pow(matrix x, int y){
matrix ans;
memset(ans.a, 0, sizeof ans);
for(int i=0; i<K; ++i) ans.a[i][i]=1;
for(; y; y>>=1, x=x*x) if(y&1) ans=ans*x;
return ans;
}
int main() {
last=cnt=1;
while(islower(s[++n]=read())) extend(s[n]-'a');
--n;
for(int i=1; i<=cnt; ++i) ++b[len[i]];
for(int i=1; i<=n; ++i) b[i]+=b[i-1];
for(int i=1; i<=cnt; ++i) a[b[len[i]]--]=i;
for(int i=cnt; i; --i){
int u=a[i];
f[u][C]=1;
for(int x=0; x<C; ++x) if(ch[u][x]) for(int j=0; j<=C; ++j)
(f[u][j]+=f[ch[u][x]][j])%=P;
else ++f[u][x];
}
A.a[C][C]=1;
for(int i=0; i<C; ++i) if(ch[1][i]) for(int j=0; j<=C; ++j)
A.a[j][i]=f[ch[1][i]][j];
B=Pow(A, 100000);
l[0][C]=1;
for(int i=0; i<=C; ++i) r[0][i]=1;
for(int i=1; i<=100000; ++i)
for(int j=0; j<K; ++j) for(int k=0; k<K; ++k)
l[i][j]=(l[i][j]+(ll)l[i-1][k]*B.a[k][j])%P,
r[i][j]=(r[i][j]+(ll)r[i-1][k]*A.a[j][k])%P;
read(q);
while(q--){
read(m);
int x=m/100000, y=m%100000, ans=0;
for(int i=0; i<K; ++i) ans=(ans+(ll)l[x][i]*r[y][i])%P;
print(ans), print('\n');
}
return flush(), 0;
}
0%