模拟赛遇到的
代码难度并不大，但是是有思维难度的。
题目链接。
题意
现在有 个单词
与 个文本串 。
设 为 在 中的出现次数，对于每一个 ：输出 。
设 。
互不相同。
题解
暴力
首先来讲
怎么做。
第一步是一个经典结论，
的取值最多有 种。
也就是说，对于一个文本串 ，最多会被匹配 次。
那么我们首先把 的 AC
自动机建出来，并记 表示，节点
的所有祖先(不包括自己)中，深度最深的，至少对应了一个单词的节点。
那么对于每一个询问串 ，我们还是先在自动机上匹配一遍。
正常计算匹配次数时，我们是暴力对 AC 自动机上所有节点做拓扑排序。
现在我们换一个思路，利用
数组。
在上面匹配的时候，每到一个节点，就在 nx 树上
dfs，并直接统计答案。
在 dfs 的过程中，若我们遍历了
次节点 ，说明这个字符串被匹配了
遍。
这样的话，我们的时间复杂度就是
的。
可以过 分，好耶。
我场上写的根号分治这部分半分钟都跑不出来
正解
首先正解有一个结论：对于所有问串，能匹配上至少一次的单词，的个数和不超过
。
形式化地：。
好，我们来证一下。
对于
的单词 ，这样的单词最多只有
个。
若 在文本串 中出现过，则 ，这样的文本串也最多只有 个。
所以这部分单词贡献的次数为
对于
的单词 ，在每一个文本串 中，一定最多只会匹配 次，因为 只有 个长度 的子串。
所以对于这种单词，贡献的次数最多也为 。
这意味这什么呢？
对于我们上面的暴力做法，只要对于每一次询问，不经过重复的节点，那么时间复杂度就是
的！
这个很简单，我们 dfs 的时候标一个 vis，dfs
的过程中直接遇到遍历过的节点，直接 return 掉。
可能有一个细节，就是这里要统计答案必须要拓扑排序，那么拓扑序如何确定呢？
比较简单，每一次 dfs 的时候，把这一条 dfs
的链，按照从深到浅的顺序，拼到当前拓扑序的前面，就是一个新的合法拓扑序
时间复杂度 ，官方题解说可以做到
，但我折磨菜，显然不会。
这里统计答案需要快速计算 ，可以使用光速幂解决。
代码
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<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using uint=unsigned int;
using ll=long long;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int L=200001;
uint p1[200005];
uint p2[200005];
int son[2000001][26];
int fail[2000001];
int id[2000001];
int nx[2000001];
char s[200005];
int T[2000001],top;
int vis[2000001];
int v[2000001];
int root;
int tim;
int cnt;
int n,m;
void ins(int &p,char *s,int i)
{
if(!p) p=++cnt;
if(!(*s))
{
id[p]=i;
return ;
}
ins(son[p][(*s)-'a'],s+1,i);
}
inline void bfs()
{
queue<int>que;fail[root]=root;
for(int i=0;i<26;i++)
{
if(!son[root][i]) son[root][i]=root;
else fail[son[root][i]]=root,que.push(son[root][i]);
}
while(!que.empty())
{
int u=que.front();que.pop();
if(id[fail[u]]) nx[u]=fail[u];
else nx[u]=nx[fail[u]];
for(int i=0;i<26;i++)
{
if(!son[u][i])
{
son[u][i]=son[fail[u]][i];
continue;
}
fail[son[u][i]]=son[fail[u]][i];
que.push(son[u][i]);
}
}
}
void dfs(int num)
{
if(!num||vis[num]==tim) return ;
vis[num]=tim;
dfs(nx[num]);
T[++top]=num;
}
inline uint get(ll v)
{
return p2[v/L]*p1[v%L];
}
inline uint solve()
{
int now=1,ok=0;tim++;
for(int i=1;s[i];i++)
{
now=son[now][s[i]-'a'];
v[now]++,dfs(now);
}
uint ans=0;
while(top)
{
int &p=T[top--];
v[nx[p]]+=v[p];
if(id[p]) ans+=get((ll)id[p]*v[p]),ok++;
v[p]=0;
}
return ans+n-ok;
}
int main()
{
read();
n=read(),m=read();
for(int i=1;i<=n;i++)
{
scanf("%s",s);
ins(root,s,i);
}
bfs();
p1[0]=p2[0]=1;
for(int i=1;i<=L;i++) p1[i]=p1[i-1]*3;
for(int i=1;i<=L;i++) p2[i]=p2[i-1]*p1[L];
for(int i=1;i<=m;i++)
{
scanf("%s",s+1);
printf("%u\n",solve());
}
return 0;
}
|
感谢观看！