【bzoj3277】【bzoj3473】串【hdu6405】Make ZYB Happy

Source and Judge

bzoj3277
bzoj3473
hdu6405

Analysis

请先思考后再展开

bzoj上的题:

方法一、后缀数组
拼起来先求个sa,然后通过枚举后缀的前缀得到子串的贡献
为了快速判断排序后区间是否来自至少k个字符串,尺取法一下即可
然后枚举每个后缀,二分位置,check用个二分表示这个长度能往左右到哪里,复杂度为两个log
然后注意到 $ans(i+1,n) \geq ans(i,n)-1$ 那么类似求hei那样暴力移动指针即可,复杂度降低为一个log

方法二、广义sam
建广义sam
然后我们希望知道每个状态出现了多少次
然后合法状态的贡献就是mx-fali.mx

子方法A:暴力跳
插入每个字符后跳nxt更新直到其他字符串留下的节点,修改其时间戳mk以及覆盖串数量cnt
然后统计答案的话(要把同一个串多次出现的统计到),就是扫每个前缀的后缀,这个随便dp一下parent树上到根路径权值即可
复杂度的证明:
跳parent的复杂度,对每个串分析,最坏为len方,但又不超过总长(时间戳)
问题转化成,

  1. $a> \sqrt n,a最多 \sqrt n 个$
  2. $a<\sqrt n,max \sum a^2 \leq \sqrt n \sum a \leq n \sqrt n$
    故总复杂度为n根号
    改进:修改parent的时候,用树链剖分,找到链上第一个mk=strid的位置
    这个可以利用strid最大的性质,线段树维护最大值的位置即可,时间为log方

子方法B:树上启发式合并
用set维护出现在哪些字符串,插入完后在parent树上启发式合并上去
这个的时空复杂度也是log方

子方法C:
可以给每个节点一个id,然后离线一下就是多次询问一个区间不同数的数量
这是个套路,离线后树状数组即可
可前往akc的blog看代码
时间复杂度为一个log

hdu:
这里只能用方法二了
没什么区别,用个差分数组,求前缀和两次即可

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
inline void chmax(ll &x,ll y) {x=x>y?x:y;}
inline void chmin(ll &x,ll y) {x=x<y?x:y;}
const int MOD=1e9+7;
ll qpower(ll x,int e)
{
ll ans=1;
while(e)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll inv(ll x) {return qpower(x,MOD-2);}
void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
int sum(int x,int y) {add(x,y);return x;}
const int MAX_N=6e5+10;
struct BIT
{
ll bit[MAX_N];BIT(){for(int i=1;i<MAX_N;i++) bit[i]=1;}
int lowbit(int x) {return x&-x;}
void mul(int x,int num) {while(x<MAX_N) bit[x]=bit[x]*num%MOD,x+=lowbit(x);}
ll ask(int x) {ll ans=1;while(x>=1) ans=ans*bit[x]%MOD,x-=lowbit(x);return ans;}
}bit;
int h[MAX_N],ans[MAX_N];
struct SAM
{
struct Nod{int son[26],fail,mx,id;}p[MAX_N];
int lst,id;
void insert(int strid,int c)
{
int now=++id;p[now].mx=p[lst].mx+1;p[now].id=strid;
int a=lst;while(a and !p[a].son[c]) p[a].son[c]=now,a=p[a].fail;
int b=p[a].son[c];
if(!b) p[now].fail=1;
else
{
if(p[b].mx==p[a].mx+1) p[now].fail=b;
else
{
int tmp=++id;p[tmp]=p[b];p[tmp].mx=p[a].mx+1;
p[b].fail=p[now].fail=tmp;
while(a and p[a].son[c]==b) p[a].son[c]=tmp,a=p[a].fail;
}
}
lst=now;
}
vector<int> son[MAX_N];
int dfn[MAX_N],dfnid,siz[MAX_N],mm[MAX_N];
void dfs(int x)
{
dfn[x]=++dfnid;siz[x]=1;mm[dfnid]=p[x].id;
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];
dfs(y);siz[x]+=siz[y];
}
}
vector<pr> qq[MAX_N];
int mul[MAX_N],nxt[MAX_N],pos[MAX_N];
void pre()
{
for(int i=1;i<=id;i++) son[p[i].fail].PB(i);
dfs(1);
for(int i=id;i>=1;i--) nxt[i]=pos[mm[i]],pos[mm[i]]=i;
for(int i=1;i<=id;i++) if(pos[i]>0) bit.mul(pos[i],h[i]);
for(int i=1;i<=id;i++) qq[dfn[i]].PB(MP(dfn[i]+siz[i]-1,i));
for(int l=1;l<=id;l++)
{
for(int t=0;t<(int)qq[l].size();t++)
mul[qq[l][t].SE]=bit.ask(qq[l][t].FR)*inv(bit.ask(l-1))%MOD;
if(nxt[l]>0) bit.mul(nxt[l],h[mm[l]]);
}
for(int i=1;i<=id;i++)
{
int l=p[p[i].fail].mx+1,r=p[i].mx;
if(l<=r) add(ans[l],mul[i]),add(ans[r+1],MOD-mul[i]);
}
}
SAM(){lst=id=1;memset(p,0,sizeof p);dfnid=0;}
}sam;
char str[MAX_N];
void main()
{
int m;scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",str+1);int ln=strlen(str+1);
sam.lst=1;for(int j=1;j<=ln;j++) sam.insert(i,str[j]-'a');
}
for(int i=1;i<=m;i++) h[i]=qread();
sam.pre();
for(int i=1;i<MAX_N;i++) add(ans[i],ans[i-1]);
for(int i=1;i<MAX_N;i++) add(ans[i],ans[i-1]);
int q;scanf("%d",&q);
while(q--)
{
int k=qread();
int all=(ll)sum(qpower(26,k+1),MOD-1)*inv(25)%MOD;add(all,MOD-1);
printf("%lld\n",(ll)ans[min(k,MAX_N-1)]*inv(all)%MOD);
}
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/8cf7.html
转载请注明出处,谢谢!