QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#504909#9111. Zayin and StringAnotherDayofSun#WA 318ms25704kbC++203.1kb2024-08-04 17:13:102024-08-04 17:13:11

Judging History

你现在查看的是最新测评结果

  • [2024-08-04 17:13:11]
  • 评测
  • 测评结果:WA
  • 用时:318ms
  • 内存:25704kb
  • [2024-08-04 17:13:10]
  • 提交

answer

#include<bits/stdc++.h>
#define N 4005
#define re
#define ll long long
#define P 998244353
using namespace std;
int n,m,K,q,T;
inline void Rd(int &res){
	re char c;res=0;
	while(c=getchar(),c<48);
	do res=(res<<3)+(res<<1)+(c^48);
	while(c=getchar(),c>47);
}
char c[N],s[N];
int to[N][30];
const double eps=1e-8;
int Pow(int x,int k){
	int res=1;
	while(k){
		if(k&1)res=1ll*res*x%P;
		x=1ll*x*x%P;
		k>>=1;
	}
	return res;
}
struct AC{
	#define M 10005
	int trie[M][26],V[M],fail[M],tot,Q[M];
	double f[4005],g[4005];
	int pre[1005][4005][2],pos[4005],pos1[4005],id[4005],id1[4005];
	void clear(){
		for(int i=0;i<=tot;i++){
			memset(trie[i],0,sizeof(trie[i]));
			V[i]=0;fail[i]=0;Q[i]=0;
		}
		for(int i=0;i<=n;i++)
			for(int j=0;j<=tot;j++)
				pre[i][j][0]=pre[i][j][1]=0;
		tot=0;
	}
	void insert(){
		scanf("%s",c+1);
		int v;Rd(v);
		int len=strlen(c+1);
		int cur=0;
		for(int i=1;i<=len;i++){
			int t=c[i]-'a';
			if(!trie[cur][t])trie[cur][t]=++tot;
			cur=trie[cur][t];
		}
		V[cur]+=v;
	}
	void Build(){
		int l=0,r=0;
		for(re int i=0;i<26;i++)if(trie[0][i]){
			fail[trie[0][i]]=0;
			Q[++r]=trie[0][i];
		}
		while(l<r){
			int x=Q[++l];
			for(re int i=0;i<26;i++)
				if(trie[x][i])fail[trie[x][i]]=trie[fail[x]][i],Q[++r]=trie[x][i];
				else trie[x][i]=trie[fail[x]][i];
		}
		for(int i=1;i<=tot;i++)
			V[i]+=V[fail[i]];
	}
	
	bool check(double v){
		for(int j=0;j<=tot;j++)f[j]=-1e15;
		f[0]=0;
		for(int i=1;i<=n;i++){
			int t=s[i]-'a';
			for(int j=0;j<=tot;j++)g[j]=f[j];
			for(int j=0;j<=tot;j++){
				g[trie[j][t]]=max(g[trie[j][t]],f[j]+V[trie[j][t]]-v);
				
			}
			for(int j=0;j<=tot;j++)f[j]=g[j];
		}
		for(int i=1;i<=tot;i++)
			if(f[i]+eps>0)return 1;
		return 0;
	}
	
	void Get(double v){
		for(int j=0;j<=tot;j++)f[j]=-1e15,pos[j]=0;
		f[0]=0;
		for(int i=1;i<=n;i++){
			int t=s[i]-'a';
			for(int j=0;j<=tot;j++)g[j]=f[j],pos1[j]=pos[j];
			for(int j=0;j<=tot;j++){
				if(g[trie[j][t]]<f[j]+V[trie[j][t]]-v){
					g[trie[j][t]]=f[j]+V[trie[j][t]]-v;
					pre[i][trie[j][t]][0]=pos[j];
					pre[i][trie[j][t]][1]=j;
					pos1[trie[j][t]]=i;
				}
				
			}
			for(int j=0;j<=tot;j++)f[j]=g[j],pos[j]=pos1[j];
		}
		int t=0;
		for(int i=0;i<=tot;i++)
			if(f[i]>f[t])t=i;
		
		ll sum=0; int len=0;
		int x=pos[t];
		while(x){
			len++;
			sum+=V[t];
			int x1=pre[x][t][0],t1=pre[x][t][1];
			x=x1,t=t1;
		}
		len=Pow(len,P-2);
		sum=sum*len%P;
		printf("%lld\n",sum);
		
	}
}A;


int main(){
	Rd(T);
	while(T--){
		Rd(n),Rd(m);
		scanf("%s",s+1);
		for(int i=1;i<=m;i++)A.insert();
		A.Build();
		for(int i=n;i>=1;i--){
			memcpy(to[i],to[i+1],sizeof(to[i]));
			to[i][s[i]-'a']=i;
		}
		
		int tim=100;
		double l=0,r=1e9,k=0;
		while(tim--){
			double mid=(l+r)*0.5;
			if(A.check(mid))k=mid,l=mid;
			else r=mid;
		}
//		printf("%.5lf\n",k);
//		A.Get(k);
		
		for(int i=1;i<=n;i++){
			int res=(int)(k*i+0.5);
			if(fabs(1.0*res/i-k)<1e-7){
				int v=Pow(i,P-2);
				res=1ll*res*v%P;
				printf("%d\n",res);
				break;
			}
		}
		
		for(int i=0;i<=n;i++)memset(to[i],0,sizeof(to[i]));
		A.clear();
		
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 318ms
memory: 25704kb

input:

80
4 7
ggeg
g 92946
d 65678
gg 50828
wrj 93954
gge 53780
a 94179
geg 40837
5 6
hiiii
ii 67984
foh 69185
hi 88153
pj 39431
i 32219
wfmve 96834
8 12
wvxxvwww
xw 1522
rzl 16262
wx 77596
v 69622
vw 82225
nykkmkv 19236
xv 83470
o 16781
w 2405
m 98319
ww 13889
qggbvty 16331
8 14
jjjiiijh
i 96670
z 74397
i...

output:

332874949
599030808
249640519
332898173
665548146
81272
61572
67112
499196918
748779217
88888
831949361
74929
665552405
499139737
665543594
332830174
60785
748771076
63646
103574
101389
465960640
332787384
249703944
89874
110460
499215461
665540622
41750
78985770
96189
111031999
94537
83443
111657
6...

result:

wrong answer 23rd lines differ - expected: '432700990', found: '465960640'