QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#620242 | #9111. Zayin and String | Mu_Silk | WA | 596ms | 123036kb | C++20 | 2.9kb | 2024-10-07 17:08:21 | 2024-10-07 17:08:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010;
const ll M=998244353;
ll qpow(ll a,ll b){
ll ans=1;
while (b){
if(b&1)ans=ans*a%M;
a=a*a%M;
b>>=1;
}
return ans;
}
struct node{
ll value=0;
int next[26]={0};
int fail;
}tree[N];
int cnt=0;
void clear(){
for(int i=0;i<=cnt;i++){
tree[i].value=0;
fill(tree[i].next,tree[i].next+26,0);
tree[i].fail=0;
}
cnt=0;
}
void insert(const string& s,ll v){
int n=s.size();
int cur=0;
for(int i=0;i<n;i++){
if(tree[cur].next[s[i]-'a']==0){
tree[cur].next[s[i]-'a']=++cnt;
}
cur=tree[cur].next[s[i]-'a'];
}
tree[cur].value+=v;
}
void build(){
queue<int> q;
for(int i=0;i<26;i++){
if(tree[0].next[i]!=0){
tree[tree[0].next[i]].fail=0;
q.push(tree[0].next[i]);
}
}
while(q.size()>0){
int x=q.front();
q.pop();
for(int i=0;i<26;i++){
if(tree[x].next[i]!=0){
tree[tree[x].next[i]].fail=tree[tree[x].fail].next[i];
q.push(tree[x].next[i]);
}
else tree[x].next[i]=tree[tree[x].fail].next[i];
}
}
for(int i=0;i<=cnt;i++){
tree[i].value+=tree[tree[i].fail].value;
}
}
struct Node{
double v;
ll a,b;
};
int n,m;
string s;
Node p[2][N];
ll ans=0;
bool check(double x){
int cur=0;
for(int i=0;i<=cnt;i++)p[cur][i]={-1e18,0,0};
p[cur][0]={0,0,0};
for(int i=0;i<s.size();i++){
for(int j=0;j<=cnt;j++)p[cur^1][j]=p[cur][j];
for(int j=0;j<=cnt;j++){
int nxtj;
if(tree[j].next[s[i]-'a']>0)nxtj=tree[j].next[s[i]-'a'];
else nxtj=tree[j].fail;
if(p[cur^1][nxtj].v<=p[cur][j].v+tree[nxtj].value-x+1e-8){
p[cur^1][nxtj].a=p[cur][j].a+tree[nxtj].value;
p[cur^1][nxtj].b=p[cur][j].b+1;
p[cur^1][nxtj].v=p[cur][j].v+tree[nxtj].value-x;
}
}
cur^=1;
}
for(int i=0;i<=cnt;i++){
if(p[cur][i].v>=0&&p[cur][i].b>0){
ans=p[cur][i].a*qpow(p[cur][i].b,M-2)%M;
// cout<<p[cur][i].v<<" "<<p[cur][i].a<<" "<<p[cur][i].b<<"\n";
return 1;
}
}
return 0;
}
void solve(){
clear();
cin>>n>>m;
cin>>s;
for(int i=0;i<m;i++){
string t;ll v;
cin>>t>>v;
insert(t,v);
}
build();
ans=0;
double l=0,r=1e18;
while(r-l>1e-8){
double m=(r+l)/2.0;
if(check(m))l=m;
else r=m;
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n=1;
cin>>n;
while(n--)solve();
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 596ms
memory: 123036kb
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 249622595 499139737 665543594 748765364 60785 748771076 63646 103574 101389 465960640 332787384 249703944 89874 110460 499215461 665540622 41750 78985770 96189 111031999 94537 83443 111657 6...
result:
wrong answer 14th lines differ - expected: '665552405', found: '249622595'