代码

#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];
int read()
{
    int data=0,w=1; char ch=0;
    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if(ch=='-'){w=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){data=data*10+ch-'0';ch=getchar();}
    return data*w;
}
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;
}

评测结果