提交记录 16208


用户 题目 状态 得分 用时 内存 语言 代码长度
zhoufangyuanPT noi17b. 【NOI2017】蚯蚓排队 Wrong Answer 76 1.191 s 390460 KB C++ 2.67 KB
提交时间 评测时间
2021-04-27 09:40:39 2021-04-27 09:41:06
#include<cstdio>
#include<cstring>
using namespace std;
inline long long mul(long long x,long long y){return x*y-(long long)((long double)x*y/100000000000000003ll)*100000000000000003ll;}
inline void read(int &x)
{
	x=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
}
int rt[51][1010000];
long long cc[210000][51];
struct node
{
	long long c;
	int cnt,next;
}tr[10010000];
int Q[10010000],head,tail;
inline int pop()
{
	int re=Q[head];
	if(head==10000000)head=1;
	else head++;
	return re;
}
inline void push(int c)
{
	Q[tail]=c;
	if(tail==10000000)tail=1;
	else tail++;
}
void ins(int len,long long c)
{
	int lst=-1;
	for(int x=rt[len][c%1000000];x!=-1;x=tr[x].next)
	{
		if(tr[x].c==c){tr[x].cnt++;return ;}
		lst=x;
	}
	int x=pop();
	tr[x].c=c;
	if(lst==-1)
	{
		rt[len][c%1000000]=x;
		tr[x].cnt=1;
		tr[x].next=-1;
	}
	else
	{
		tr[lst].next=x;
		tr[x].cnt=1;
		tr[x].next=-1;
	}
}
void era(int len,long long c)
{
	int lst=-1;
	for(int x=rt[len][c%1000000];x!=-1;x=tr[x].next)
	{
		if(tr[x].c==c)
		{
			tr[x].cnt--;
			if(tr[x].cnt==0)
			{
				if(lst==-1)rt[len][c%1000000]=-1;
				else tr[lst].next=tr[x].next;
				push(x);
			}
			break;
		}
		lst=x;
	}
}
int fin(int len,long long c)
{
	int s=0;
	for(int x=rt[len][c%1000000];x!=-1;x=tr[x].next)if(tr[x].c==c)s+=tr[x].cnt;
	return s;
}
struct Lian
{
	int last,next;
}L[210000];
int a[210000];
char st[10010000];
int main()
{
	int n,m;read(n);read(m);
	memset(rt,-1,sizeof(rt));
	head=1;tail=10000000;
	for(int i=1;i<=10000000;i++)Q[i]=i;
	for(int i=1;i<=n;i++)
	{
		read(a[i]);
		cc[i][1]=a[i];
		ins(1,a[i]);
		L[i].last=L[i].next=-1;
	}
	for(int i=1;i<=m;i++)
	{
		int opt;read(opt);
		if(opt==1)
		{
			int x,y;read(x);read(y);
			L[x].next=y;L[y].last=x;
			for(int j=1,X=x;j<50&&X!=-1;j++,X=L[X].last)
			{
				for(int k=1,Y=y;j+k<=50&&Y!=-1;k++,Y=L[Y].next)
				{
					cc[X][j+k]=(cc[X][j+k-1]*17+a[Y])%100000000000000003ll;
					ins(j+k,cc[X][j+k]);
				}
			}
		}
		else if(opt==2)
		{
			int x;read(x);
			int k=1;
			for(int X=L[x].next;k<=50&&X!=-1;k++,X=L[X].next);
			k--;
			L[L[x].next].last=-1;
			L[x].next=-1;
			for(int j=1,X=x;j<50&&X!=-1;j++,X=L[X].last)
			{
				for(int kk=1;j+kk<=50&&kk<=k;kk++)era(j+kk,cc[X][j+kk]);
			}
		}
		else if(opt==3)
		{
			scanf("%s",st+1);
			int len=strlen(st+1);
			int k;read(k);
			long long c=0,g=1;
			for(int kk=1;kk<=k;kk++)c=(c*17+st[kk]-'0')%100000000000000003ll;
			for(int kk=1;kk<k;kk++)g=g*17%100000000000000003ll;
			long long ss=fin(k,c);
			for(int j=2;j+k-1<=len;j++)
			{
				c=((c-mul((st[j-1]-'0'),g)+100000000000000003ll)*17+st[j+k-1]-'0')%100000000000000003ll;
				ss=ss*fin(k,c)%998244353;
			}
			printf("%lld\n",ss);
		}
	}
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #122.252 ms234 MB + 692 KBAcceptedScore: 4

Testcase #221.909 ms234 MB + 700 KBAcceptedScore: 4

Testcase #332.684 ms236 MB + 992 KBAcceptedScore: 4

Testcase #422.244 ms234 MB + 948 KBAcceptedScore: 4

Testcase #529.849 ms235 MB + 360 KBAcceptedScore: 4

Testcase #6188.662 ms274 MB + 360 KBAcceptedScore: 4

Testcase #755.174 ms254 MB + 716 KBAcceptedScore: 4

Testcase #8123.9 ms270 MB + 464 KBAcceptedScore: 4

Testcase #9193.7 ms275 MB + 376 KBWrong AnswerScore: 0

Testcase #10218.284 ms271 MB + 524 KBAcceptedScore: 4

Testcase #11368.914 ms281 MB + 484 KBWrong AnswerScore: 0

Testcase #12214.537 ms296 MB + 152 KBAcceptedScore: 4

Testcase #1394.569 ms274 MB + 752 KBAcceptedScore: 4

Testcase #14246.37 ms303 MB + 732 KBAcceptedScore: 4

Testcase #15302.608 ms306 MB + 960 KBWrong AnswerScore: 0

Testcase #16458.538 ms306 MB + 180 KBAcceptedScore: 4

Testcase #17633.777 ms315 MB + 464 KBWrong AnswerScore: 0

Testcase #18756.425 ms373 MB + 716 KBAcceptedScore: 4

Testcase #19883.48 ms381 MB + 72 KBAcceptedScore: 4

Testcase #20226.503 ms329 MB + 116 KBAcceptedScore: 4

Testcase #21180.197 ms314 MB + 816 KBAcceptedScore: 4

Testcase #22536.848 ms368 MB + 96 KBAcceptedScore: 4

Testcase #23578.86 ms369 MB + 668 KBWrong AnswerScore: 0

Testcase #241.003 s372 MB + 944 KBAcceptedScore: 4

Testcase #251.191 s381 MB + 316 KBWrong AnswerScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2021-05-17 10:56:32 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用