LOJ2303 「NOI2017」蚯蚓排队

「NOI2017」蚯蚓排队

题目描述

蚯蚓幼儿园有$n$只蚯蚓。幼儿园园长神刀手为了管理方便,时常让这些蚯蚓们列队表演。

所有蚯蚓用从$1$到$n$的连续正整数编号。每只蚯蚓的长度可以用一个正整数表示,根据入园要求,所有蚯蚓的长度都不超过$6$。神刀手希望这些蚯蚓排成若干个队伍,初始时,每只蚯蚓各自排成一个仅有一只蚯蚓的队伍,该蚯蚓既在队首,也在队尾。

神刀手将会依次进行$m$次操作,每个操作都是以下三种操作中的一种:

  1. 给出$i$和$j$,令$i$号蚯蚓与$j$号蚯蚓所在的两个队伍合并为一个队伍,具体来说,令$j$号蚯蚓紧挨在$i$号蚯蚓之后,其余蚯蚓保持队伍的前后关系不变。

  2. 给出$i$,令$i$号蚯蚓与紧挨其后的一只蚯蚓分离为两个队伍,具体来说,在分离之后,$i$号蚯蚓在其中一个队伍的队尾,原本紧挨其后的那一只蚯蚓在另一个队伍的队首,其余蚯蚓保持队伍的前后关系不变。

  3. 给出一个正整数$k$和一个长度至少为$k$的数字串$s$,对于$s$的每个长度为$k$的连续子串$t$(这样的子串共有$|s| - k + 1$ 个,其中$|s|$为$s$的长度),定义函数$f(t)$,询问所有这些$f(t)$的乘积对$998244353$取模后的结果。其中$f(t)$的定义如下: 对于当前的蚯蚓队伍,定义某个蚯蚓的向后$k$数字串为:从该蚯蚓出发,沿队伍的向后方向,寻找最近的$k$只蚯蚓(包括其自身),将这些蚯蚓的长度视作字符连接而成的数字串;如果这样找到的蚯蚓不足$k$只,则其没有向后$k$数字串。例如蚯蚓的队伍为$10$号蚯蚓在队首,其后是$22$号蚯蚓,其后是$3$号蚯蚓(为队尾),这些蚯蚓的长度分别为$4$、$5$、$6$,则$10$号蚯蚓的向后$3$数字串456,$22$号蚯蚓没有向后$3$数字串,但其向后$2$数字串56,其向后$1$数字串5

而$f(t)$表示所有蚯蚓中,向后$k$数字串恰好为$t$的蚯蚓只数。

输入输出格式

输入格式:

输入文件的第一行有两个正整数$n,m$ ,分别表示蚯蚓的只数与操作次数。

第二行包含$n$个不超过$6$的正整数,依次表示编号为$1, 2, \dots , n$的蚯蚓的长度。

接下来$m$行,每行表示一个操作。每个操作的格式可以为:

  • 1 i j $(1 \leqslant i, j \leqslant n)$表示:令$i$号与$j$号蚯蚓所在的两个队伍合并为一个队伍,新队伍中,$j$号蚯蚓紧挨在$i$号蚯蚓之后。保证在此操作之前,$i$ 号蚯蚓在某个队伍的队尾,$j$号蚯蚓在某个队伍的队首,且两只蚯蚓不在同一个队伍中。

  • 2 i $(1 \leqslant i \leqslant n)$表示:令$i$号蚯蚓与紧挨其后一个蚯蚓分离为两个队伍。保证在此操作之前,$i$号蚯蚓不是某个队伍的队尾。

  • 3 s k ($k$为正整数,$s$为一个长度至少为$k$的数字串)表示:询问$s$的每个长度为$k$的子串$t$的$f(t)$的乘积,对$998244353$取模的结果。$f(t)$的定义见题目描述。

同一行输入的相邻两个元素之间,用恰好一个空格隔开。

输入文件可能较大,请不要使用过于缓慢的读入方式。

输出格式:

依次对于每个形如3 s k的操作,输出一行,仅包含一个整数,表示询问的结果。

输入输出样例

输入样例#1: 复制
5 9
3 1 3 5 3
3 333135 2
3 333135 1
1 1 3
1 2 5
1 3 2
1 5 4
3 333135 2
3 333135 1
3 333135 3
输出样例#1: 复制
0
81
1
81
0
输入样例#2: 复制
2 10
6 6
3 666666 1
1 1 2
3 666666 2
3 666666 4
3 666666666666666666666666666666 1
2 1
1 2 1
3 666666 2
3 666666 4
3 666666666666666666666666666666 1
输出样例#2: 复制
64
1
0
75497471
1
0
75497471

说明

【子任务】

保证$n \leqslant 2 \times 10^5,\ m \leqslant 5 \times 10^5,\ k \leqslant 50$。

设$\Sigma |S|$为某个输入文件中所有询问的 s 的长度总和,则$\Sigma |S| \leqslant 10^7$。 设$c$为某个输入文件中形如2 i的操作的次数,则$c \leqslant 10^3$ 。

每个测试点的详细信息见下表:

LOJ2303 「NOI2017」蚯蚓排队

题解

\(k\le 50\),那么变动的量也很少,直接用hash表维护长度和字符串hash值就行了。

至于蚯蚓,使用链表维护即可。

我不开O2就TLE最后一个点,2015ms。毒瘤出题人卡常数。

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
    for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef unsigned long long ull;

co int MAX=222222,MOD=998244353,base=233;
char ch[10000010];
ull pw[MAX];
int next[MAX],last[MAX],a[MAX];
int n,m;
co int mod=19260817;
struct Hash_Table{
    int h[mod],cnt;
    struct Line{int len,next,w;ull s;}e[10000000];
    void add(int len,ull s,int w){
        for(rg int i=h[s%mod];i;i=e[i].next)
            if(e[i].len==len&&e[i].s==s)
                return (e[i].w+=w)%=MOD,void();
        e[++cnt]=(Line){len,h[s%mod],w,s},h[s%mod]=cnt;
    }
    int query(int len,ull s){
        for(rg int i=h[s%mod];i;i=e[i].next)
            if(e[i].len==len&&e[i].s==s) return e[i].w;
        return 0;
    }
}hash;
void link(int x,int y){
    next[x]=y,last[y]=x;
    ull sx=0;
    for(int i=x,lx=1;i&&lx<=49;i=last[i],++lx){
        sx+=a[i]*pw[lx-1];
        ull sy=sx;
        for(int j=y,ly=lx+1;j&&ly<=50;j=next[j],++ly) sy=sy*base+a[j],hash.add(ly,sy,1);
    }
}
void cut(int x){
    int y=next[x];
    ull sx=0;
    for(rg int i=x,lx=1;i&&lx<=49;i=last[i],++lx){
        sx+=a[i]*pw[lx-1];
        ull sy=sx;
        for(rg int j=y,ly=lx+1;j&&ly<=50;j=next[j],++ly) sy=sy*base+a[j],hash.add(ly,sy,MOD-1);
    }
    next[x]=last[y]=0;
}
int query(int len){
    int l=strlen(ch+1),ans=1;
    ull s=0;
    for(rg int i=1;i<len;++i) s=s*base+ch[i]-'0';
    ch[0]='0';
    for(rg int i=len;i<=l;++i){
        s=s*base+ch[i]-'0'-pw[len]*(ch[i-len]-'0');
        ans=1LL*ans*hash.query(len,s)%MOD;
    }
    return ans;
}
int main(){
    std::ios::sync_with_stdio(0);
    pw[0]=1;for(rg int i=1;i<=50;++i) pw[i]=pw[i-1]*base;
    read(n),read(m);
    for(rg int i=1;i<=n;++i) hash.add(1,read(a[i]),1);
    while(m--){
        int opt=read<int>();
        if(opt==1){
            int x=read<int>(),y=read<int>();
            link(x,y);
        }
        else if(opt==2) cut(read<int>());
        else{
            scanf("%s",ch+1);
            printf("%d\n",query(read<int>()));
        }
    }
    return 0;
}
上一篇:Maixpy的k210tf卡入手教程


下一篇:K210套件实现人脸识别