有趣的 Suffix virtual Tree。
显然对询问的后缀建虚树即可……
代码： 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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
using namespace std;
const int N = 5e5;
const int M = 3e6;
const long long mod = 23333333333333333;
int n,m,t;
char s[N + 5];
int pos[N + 5];
long long ans;
namespace SAM
{
struct node
{
int ch[26];
int fa,len;
} sam[(N << 1) + 5];
int las = 1,tot = 1;
inline void insert(int x)
{
int cur = las,p = ++tot;
sam[p].len = sam[cur].len + 1;
for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
sam[cur].ch[x] = p;
if(!cur)
sam[p].fa = 1;
else
{
int q = sam[cur].ch[x];
if(sam[cur].len + 1 == sam[q].len)
sam[p].fa = q;
else
{
int nxt = ++tot;
sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
sam[cur].ch[x] = nxt;
}
}
las = p;
}
int to[(N << 1) + 5],pre[(N << 1) + 5],first[(N << 1) + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int dep[(N << 1) + 5],sz[(N << 1) + 5],son[(N << 1) + 5],top[(N << 1) + 5],id[(N << 1) + 5],rk[(N << 1) + 5];
void dfs(int p)
{
static int tot = 0;
sz[rk[id[p] = ++tot] = p] = 1;
for(register int i = first[p];i;i = pre[i])
dep[to[i]] = dep[p] + 1,
dfs(to[i]),
sz[p] += sz[to[i]],
son[p] = max(son[p],to[i],[](int x,int y)
{
return sz[x] < sz[y];
});
}
inline void build()
{
for(register int i = 2;i <= tot;++i)
add(sam[i].fa,i);
dfs(1);
for(register int i = 1;i <= tot;++i)
top[rk[i]] = rk[i] == son[sam[rk[i]].fa] ? top[sam[rk[i]].fa] : rk[i];
}
inline int getlca(int x,int y)
{
while(top[x] ^ top[y])
dep[top[x]] > dep[top[y]] ? (x = sam[top[x]].fa) : (y = sam[top[y]].fa);
return dep[x] < dep[y] ? x : y;
}
}
namespace VT
{
int to[(N << 1) + 5],pre[(N << 1) + 5],first[(N << 1) + 5],edge_tot;
inline void add(int u,int v)
{
int &tot = edge_tot;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int sz[(N << 1) + 5];
int key[M + 5],tot;
int s[(N << 1) + 5],top;
inline void build()
{
sort(key + 1,key + tot + 1,[](int x,int y)
{
return SAM::id[x] < SAM::id[y];
}),tot = unique(key + 1,key + tot + 1) - key - 1;
top = edge_tot = 0,first[s[++top] = 1] = sz[1] = 0;
for(register int i = 1,lca;i <= tot;++i)
{
if(key[i] ^ 1)
{
lca = SAM::getlca(key[i],s[top]);
if(lca ^ s[top])
{
for(;SAM::id[lca] < SAM::id[s[top - 1]];add(s[top - 1],s[top]),--top);
if(SAM::id[lca] > SAM::id[s[top - 1]])
first[lca] = sz[lca] = 0,add(lca,s[top]),s[top] = lca;
else
add(lca,s[top--]);
}
first[s[++top] = key[i]] = 0;
}
sz[key[i]] = 1;
}
for(;top > 1;add(s[top - 1],s[top]),--top);
--top;
}
void dfs(int p)
{
for(register int i = first[p];i;i = pre[i])
dfs(to[i]),
ans = (ans + (long long)SAM::sam[p].len * sz[p] % mod * sz[to[i]]) % mod,
sz[p] += sz[to[i]];
}
}
int main()
{
scanf("%d%d%s",&n,&m,s + 1);
for(register int i = n;i;--i)
SAM::insert(s[i] - 'a'),pos[i] = SAM::las;
SAM::build();
for(;m;--m)
{
scanf("%d",&t),VT::tot = ans = 0;
for(int x;t;--t)
scanf("%d",&x),VT::key[++VT::tot] = pos[x];
VT::build(),VT::dfs(1);
printf("%lld\n",ans);
}
}