题解 P3823 【[NOI2017]蚯蚓排队】
gongbangrui · · 题解
题意
给定n条长度不超过6的蚯蚓，初始各自在一个队伍。m次操作：1.将i号蚯蚓和j号蚯蚓的队伍合并（保证i为队尾，j为队首）。2.将i号蚯蚓和它后面的蚯蚓分离成两个队。3.询问：给定字符串S和正整数k，求f(每个长度为k的子串)的乘积。其中f(S)定义为蚯蚓在其队伍向后延伸k位组成的字符串等于S的蚯蚓个数。(n \leq 210^5,m \leq 510^5,k \leq 50,\sum |s| \leq 10^7,c \leq 10^3)，其中c为操作2的数量。
算法分析
模拟+hash 暴力一点考虑，每个队伍维护一条链，合并和分裂时维护(c_{x,i})表示第x号蚯蚓向后延伸i位的字符串hash值并更新长度为i的答案，查询的时候直接枚举子串访问长度为i的答案中hash值相同的。 容易知道这样最坏复杂度是(O(mk^2+\sum |s|))，理论上依然无法通过。
继续分析。 考虑分离操作至多c次，复杂度为(O(ck^2))。 考虑合并操作，因为每次合并其实显然是不需要枚举满的，是否有可能省去一个k的复杂度？合并的终串中每个子串只会被统计一次（分离只有1000次，不影响复杂度），而总共有nk个子串，所以复杂度为(O(mk))。
总复杂度(O(ck^2+mk+\sum |s|))。 注意：我用的hash方式是一个小哈希存邻接表，一个大哈希当成真实值来检验。
AC代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int P=19260817;
const int N=P+10;
const int M=2e5+5;
const int B=17;
int read()
{
int ret=0,op=1,c=getchar();
while(c>'9' || c<'0')
{
if(c=='-') op=-1;
c=getchar();
}
while(c>='0' && c<='9')
{
ret=ret*10+c-'0';
c=getchar();
}
return ret*op;
}
int ecnt=0,head[N];
int n,m;
int nxt[M],lst[M],val[M];//nxt和lst为维护蚯蚓位置的链表
ll powB[100],pow10[100],qwq[100];
char s[10000005];
struct edge
{
int next,cnt,last;
ll w;
}e[N];
void add(ll hash,ll q)//哈希表，如果有对于hash这个哈希值有q这个原值则cnt++，否则新开一个点
{
//printf("add:%lld:%lld\n",hash,q);
for(int i=head[hash];i;i=e[i].next)
if(e[i].w==q)
{
e[i].cnt++;
return ;
}
e[++ecnt].cnt=1;
e[ecnt].w=q;
e[ecnt].next=head[hash];
head[hash]=ecnt;
}
void dlt(ll hash,ll q)//与add同理
{
for(int i=head[hash];i;i=e[i].next)
if(e[i].w==q)
{
e[i].cnt--;
return ;
}
}
int query(ll hash,ll q)//与add同理
{
for(int i=head[hash];i;i=e[i].next) if(e[i].w==q) return e[i].cnt;
return 0;
}
int s1[100],s2[100];
void link(int u,int v)
{
int l1=0,l2=0;
ll hsh=0,q=0,haxi=0,Q=0;
nxt[u]=v;
lst[v]=u;
for(int i=u;i&&l1<49;i=lst[i])
s1[++l1]=val[i],hsh=(hsh+val[i]*powB[l1-1])%P,q=q+val[i]*pow10[l1-1];//将u与u之前最长50的串取出来，注意在s1中的串是反着的
for(int i=v;i&&l2<49;i=nxt[i]) s2[++l2]=val[i];
for(int i=l1;i>=1;i--)//s1是反串，最前面的字符在l1的位置，所以倒序枚举
{
haxi=0;Q=0;
for(int j=1;j<=l2&&i+j<=50;j++)
{
haxi=(haxi*B+s2[j])%P;
Q=Q*10+s2[j];
add((hsh*powB[j]%P+haxi)%P,q*pow10[j]+Q);
}
hsh=((hsh-powB[i-1]*s1[i])%P+P)%P;
q=q-pow10[i-1]*s1[i];
}
}
void cut(int u,int v)//与link同理
{
int l1=0,l2=0;
ll hsh=0,q=0,haxi=0,Q=0;
nxt[u]=0;
lst[v]=0;
for(int i=u;i&&l1<49;i=lst[i])
s1[++l1]=val[i],hsh=(hsh+val[i]*powB[l1-1])%P,q=q+val[i]*pow10[l1-1];
for(int i=v;i&&l2<49;i=nxt[i]) s2[++l2]=val[i];
for(int i=l1;i>=1;i--)
{
haxi=0;Q=0;
for(int j=1;j<=l2&&i+j<=50;j++)
{
haxi=(haxi*B+s2[j])%P;
Q=Q*10+s2[j];
dlt((hsh*powB[j]%P+haxi)%P,q*pow10[j]+Q);
}
hsh=((hsh-powB[i-1]*s1[i])%P+P)%P;
q=q-pow10[i-1]*s1[i];
}
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) val[i]=read(),qwq[val[i]]++;
powB[0]=pow10[0]=1;
for(int i=1;i<=50;i++) powB[i]=powB[i-1]*B%P,pow10[i]=pow10[i-1]*10;
int op,x,y;
while(m--)
{
op=read();
if(op==1)
{
x=read(),y=read();
link(x,y);
}
else if(op==2)
{
x=read();
cut(x,nxt[x]);
}
else
{
int k;
scanf("%s%d",s+1,&k);
int len=strlen(s+1);
ll hsh=0,q=0,ans=1;
if(k==1)//特别的，如果询问长度为1的串，因为之前我也没有加过，所以在读入的时候开一个桶来统计答案
{
for(int i=1;i<=len;i++) ans=ans*qwq[s[i]-'0']%mod;
printf("%lld\n",ans%mod);
continue;
}
for(int i=1;i<=k;i++)
{
hsh=(hsh*B+s[i]-'0')%P;
q=q*10+s[i]-'0';
}
// printf("(%lld)%lld->",hsh,q);
ans=query(hsh,q)%mod;
for(int i=k+1;i<=len;i++)
{
hsh=(((hsh-(s[i-k]-'0')*powB[k-1])%P+P)%P*B+s[i]-'0')%P;
q=((q-(s[i-k]-'0')*pow10[k-1]))*10+s[i]-'0';
// printf("(%lld)%lld->",hsh,q);
ans=ans*query(hsh,q)%mod;
}
printf("%lld\n",ans);
}
}
return 0;
}