代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int k=50,mod=998244353;
int n,m,len,y[10000002],t[8][20000002];
long long ans;
char ch[10000002];
typedef struct{
    int w,las,nex;
}P;
P p[200002];
char buf[100000],*pp1=buf,*pp2=buf;
inline char nc()
{
    return pp1==pp2 && (pp2=(pp1=buf)+fread(buf,1,100000,stdin),pp1==pp2) ? EOF : *pp1++;
}
inline int read()
{ 
    char ch;int x=0;bool f=0;
    while((ch=nc())<48)if(ch==45)break;
    if(ch==45)f=1;else x=ch-48;
    while((ch=nc())>=48)x=(x<<1)+(x<<3)+ch-48;
    return f ? -x : x;
}
int main()
{
    n=read();m=read();
    for (int i=1;i<=n;i++)
    {
        p[i].w=read();p[i].las=p[i].nex=-1;
        if (!t[p[i].w][0])t[p[i].w][0]=++len;
        t[0][t[p[i].w][0]]++;
    }
    while(m--)
    {
        int u;
        u=read();
        if (u==1)
        {
            int a,b,c,root;bool u;
            a=read();b=read();
            p[a].nex=b;p[b].las=a;
            for (int i=a;i!=-1;i=p[i].las)
            {
                c=u=root=0;
                for (int j=i;c<k&&j!=-1;j=p[j].nex)
                {
                    if (!t[p[j].w][root])
                    {
                        t[p[j].w][root]=++len;
                        if (t[7][root]==-1 || !t[p[j].w][t[7][root]])
                        t[7][len]=-1;
                        else t[7][len]=t[p[j].w][t[7][root]];
                    }
                    root=t[p[j].w][root];
                    if (j==b)u=1;t[0][root]+=u;
                    c++;
                }
                if (!u)break;
            }
        }
        else if (u==2)
        {
            int a,b,c,root;bool u;
            a=read();b=p[a].nex;
            for (int i=a;i!=-1;i=p[i].las)
            {
                c=u=0;root=0;
                for (int j=i;c<k&&j!=-1;j=p[j].nex)
                {
                    root=t[p[j].w][root];
                    if (j==b)u=1;t[0][root]-=u;
                    c++;
                }
                if (!u)break;
            }
            p[a].nex=p[b].las=-1;
        }
        else
        {
            int a,l,root=0;ans=0;
            scanf("%s",ch);a=read();l=strlen(ch);
            for (int i=0;i<a;i++)
            {
                root=t[ch[i]-48][root];if (!root)goto ccj;
            }
            ans=t[0][root];
            for (int i=a;i<l;i++)
            {
                root=t[7][root];if (root<0){ans=0;goto ccj;}
                root=t[ch[i]-48][root];if (!root){ans=0;goto ccj;}
                ans=ans*t[0][root]%mod;
            }
            ccj:printf("%lld\n",ans);
        }
    }
    return 0;
}

评测结果