QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#504886 | #9111. Zayin and String | AnotherDayofSun# | WA | 324ms | 24744kb | C++20 | 3.1kb | 2024-08-04 16:58:30 | 2024-08-04 16:58:31 |
Judging History
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=0;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+1e-6);
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: 324ms
memory: 24744kb
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'