QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#625568 | #9111. Zayin and String | expectant | AC ✓ | 493ms | 51168kb | C++14 | 3.0kb | 2024-10-09 19:54:29 | 2024-10-09 19:54:30 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=(k);++i)
#define drp(i,j,k) for(int i=j;i>=(k);--i)
#define isdigit(ch) (ch>=48&&ch<=57)
#define mp std::make_pair
#define mod 998244353
#define MAXN 1000005
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
inline int read(){
int x=0;
bool sgn=true;
char ch=getchar();
while(!isdigit(ch)) sgn^=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return sgn?x:-x;
}
inline ll readll(){
ll x=0;
bool sgn=true;
char ch=getchar();
while(!isdigit(ch)) sgn^=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return sgn?x:-x;
}
template <typename tp> inline tp min(tp x,tp y){return x<y?x:y;}
template <typename tp> inline tp max(tp x,tp y){return x>y?x:y;}
template <typename tp> inline bool chkmin(tp &x,tp y){return x>y&&(x=y,true);}
template <typename tp> inline bool chkmax(tp &x,tp y){return x<y&&(x=y,true);}
int task,n,m;
char a[MAXN];
ld f[1005][4005];
namespace acam{
int pos;
std::queue<int> q;
struct node{
int ch[26];
int fail;
ll sum;
}tree[MAXN];
inline void init(){
std::queue<int>().swap(q);
while(pos){
memset(tree[pos].ch,0,sizeof(tree[pos].ch));
tree[pos].fail=0,tree[pos].sum=0,--pos;
}
pos=1;
}
inline void ins(const std::string &s,ll val){
int u=1;
for(auto x:s){
int id=x-'a';
if(!tree[u].ch[id]) tree[u].ch[id]=++pos;
u=tree[u].ch[id];
}
tree[u].sum+=val;
}
inline void bfs(){
q.push(1);
rep(i,0,25) tree[0].ch[i]=1;
while(!q.empty()){
int u=q.front();
tree[u].sum+=tree[tree[u].fail].sum,q.pop();
rep(i,0,25){
int v=tree[u].ch[i],fail=tree[u].fail;
if(!v) tree[u].ch[i]=tree[fail].ch[i];
else tree[v].fail=tree[fail].ch[i],q.push(v);
}
}
}
inline int trans(int x,char y){
return tree[x].ch[y-'a'];
}
inline ll getval(int x){
return tree[x].sum;
}
}
inline ll pw(int x,int y){
ll base=x,ret=1;
for(;y;y>>=1,(base*=base)%=mod) if(y&1) (ret*=base)%=mod;
return ret;
}
inline bool chk(ld x){
rep(i,0,n) rep(j,0,acam::pos) f[i][j]=-1e18;
f[0][1]=0;
rep(i,0,n-1) rep(j,1,acam::pos){
if(f[i][j]==-1e18) continue;
int k=acam::trans(j,a[i+1]);
chkmax(f[i+1][j],f[i][j]);
chkmax(f[i+1][k],f[i][j]+acam::getval(k)-x);
}
return *std::max_element(f[n]+1,f[n]+acam::pos+1)>0;
}
inline ll solve(){
ld l=0,r=1e8;
while(r-l>1e-7){
ld mid=(l+r)/2;
if(chk(mid)) l=mid;
else r=mid;
}
int x=0,y=1;
ld rst=r-floorl(r);
rep(i,1,n) rep(j,1,i-1){
if((ld)j/i>rst+1e-7) continue;
if(j*y>i*x) x=j,y=i;
}
return (((ll)r)+x*pw(y,mod-2))%mod;
}
int main(){
drp(task,read(),1){
n=read(),m=read(),scanf("%s",a+1);
acam::init();
rep(i,1,m){
std::string s;
ll val=0;
std::cin>>s,val=read();
acam::ins(s,val);
}
acam::bfs();
printf("%lld\n",solve());
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 441ms
memory: 40428kb
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 432700990 332787384 249703944 89874 110460 499215461 665540622 41750 782592345 96189 111031999 94537 83443 111657 ...
result:
ok 80 lines
Test #2:
score: 0
Accepted
time: 439ms
memory: 34628kb
input:
80 6 9 ffdffd df 5764 g 80673 dfd 93960 sje 2655 f 52989 dykez 24524 fd 93464 v 5951 dd 80386 4 8 hgig hi 36540 eoy 56555 hgi 16024 da 39472 i 11615 w 28388 h 13233 b 36396 3 6 jhh jhh 78310 jck 52810 h 93391 f 84166 j 58232 tixuja 90170 6 9 wvuuwu uu 18802 cto 64653 v 17516 e 89244 vu 7176 yb 35851...
output:
499220334 30694 665604010 28868 499155869 399434929 43201 55925 53130 665596997 112603 48316 51377 665595637 332817598 92435 332790461 199775438 118514 46654 98424 99849 468077048 33082 499180262 499161147 99170 49530 249661952 665599894 19760011 31724 125134 665598061 665568382 53270 57347 74873729...
result:
ok 80 lines
Test #3:
score: 0
Accepted
time: 461ms
memory: 49124kb
input:
80 6 9 fdfdfd f 62278 bd 63301 d 82508 hyx 79679 fd 77199 gat 3304 dd 38771 sz 65675 ffd 39030 3 4 ihi i 23765 vum 4334 ihi 35317 jz 58824 7 12 nmnnnmn mm 53554 z 37003 nnm 93166 os 47375 n 91295 k 23069 mn 70863 ke 53536 nmm 79577 xx 80568 nnn 9319 xpoioy 49090 3 4 stu su 64015 pm 39855 stu 12774 g...
output:
249677224 665523851 499231655 499154184 95658 332794463 499226034 748789158 80649 144255 249638234 499158453 48294 249637902 90840 499168402 499173301 499254931 599034136 249676514 332790820 798677117 102014068 332796115 44767 96925 120384 499168015 88966 99986 27092909 66644 832034701 125185 332785...
result:
ok 80 lines
Test #4:
score: 0
Accepted
time: 493ms
memory: 51168kb
input:
80 7 12 jihijhj i 72948 zl 98729 hjh 84734 r 57189 hh 75314 yn 6123 jh 73861 u 47490 jhj 86000 vi 60571 j 69646 rzeaekb 51127 3 6 rrr r 47818 c 7921 rr 7750 aq 79014 rrr 28438 igv 43270 6 8 jkijkj k 23174 xs 49356 j 68561 xw 31342 kk 97855 flt 49385 kij 10232 xy 84681 6 8 klkmml kl 29970 chw 4110 lk...
output:
399420420 62464 499194278 499164004 665521173 499197753 332808457 44186 665604467 97158 831965037 665545040 665623667 97887 665633265 58787 249631705 90776 332775392 75134 18376 798687225 25718328 332778936 47597 121972 44629 665528383 499213995 748819760 73157720 80450 698915455 249699722 499140797...
result:
ok 80 lines
Test #5:
score: 0
Accepted
time: 461ms
memory: 42940kb
input:
80 3 4 bbb b 44630 kt 93484 bb 29609 ps 66781 6 8 ttttut ttu 29879 lh 47140 tu 38786 lel 2159 ttt 63824 e 42744 tt 84477 a 135 8 13 qqqqqpoo po 18783 pt 34823 qpo 1940 mh 66501 qq 68822 tdr 21257 o 59431 fxh 58424 q 18175 or 99541 p 43971 tqnmjr 34605 qqq 92858 4 8 uwvv v 86612 ig 38634 uv 21955 c 5...
output:
332812487 105876 199777818 102222 70120 332840767 79049 332835764 54271 99337 460834412 665570126 56347 99619 30473 499283122 499229142 499208844 49412 665558243 748735960 332866356 737994449 499188739 499230438 34815 332868289 665538255 332834232 94334 244225146 499231229 844832371 199748229 108136...
result:
ok 80 lines