QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#532663 | #9111. Zayin and String | ZYLZPP | WA | 101ms | 32324kb | C++20 | 2.7kb | 2024-08-25 08:24:46 | 2024-08-25 08:24:47 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define For(i, l, r) for (int i = (l); i <= (r); ++i)
typedef long long ll;
typedef double lf;
const int N = 1e3 + 5, S = 4e3 + 5, Mo = 998244353;
const lf eps = 1e-8;
inline int ml(const int &x, const int &y) { return 1ll * x * y % Mo; }
inline void mul(int &x, const int &y) { x = ml(x, y); }
inline int qPow(int a, int b) { int r=1; for (;b;b>>=1,mul(a,a)) if (b&1) mul(r,a); return r; }
template<class C> inline bool cmax(C &x, const C &y) { return y>x? x=y, 1: 0; }
struct IO {
char c; int f;
#define gc() (getchar())
template<class C>
inline IO& operator >> (C &x) {
x = 0; f = 1;
while (!isdigit(c = gc()) && ~c) f |= -!(c ^ 45);
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
x *= f; return *this;
}
inline bool operator ~ () { return ~c; }
} io;
int T, n, m, vis[N][S], tim;
lf f[N][S];
char t[N];
namespace ACAM {
int ch[S][26], tot = 1, fail[S], sum[S];
char s[S];
inline void add(char s[], int x) {
int n = strlen(s + 1), u = 1;
For (i, 1, n) {
int c = s[i] - 'a';
if (!ch[u][c]) ch[u][c] = ++tot;
u = ch[u][c];
}
sum[u] += x;
}
inline void build() {
For (i, 0, 25) ch[0][i] = 1;
queue<int > q; q.push(1);
fail[1] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
For (i, 0, 25) (ch[u][i]? q.push(ch[u][i]), fail[ch[u][i]]: ch[u][i]) = ch[fail[u]][i];
}
}
}
using namespace ACAM;
inline bool ok(lf x) {
tim++;
f[0][1] = 0; vis[0][1] = tim;
For (i, 0, n - 1) For (j, 1, tot) if (vis[i][j] == tim) {
int c = t[i + 1] - 'a', k = ch[j][c];
if (vis[i + 1][j] ^ tim) vis[i + 1][j] = tim, f[i + 1][j] = f[i][j];
else cmax(f[i + 1][j], f[i][j]);
if (vis[i + 1][k] ^ tim) vis[i + 1][k] = tim, f[i + 1][k] = f[i][j] + sum[k] - x;
else cmax(f[i + 1][k], f[i][j] + sum[k] - x);
}
For (i, 1, tot) if (vis[n][i] == tim && f[n][i] > eps) return 1;
return 0;
}
inline void solve() {
For (i, 1, tot) fail[i] = sum[i] = 0, memset(ch[i], 0, sizeof ch[i]);
tot = 1;
io >> n >> m;
scanf("%s", t + 1);
int x;
For (i, 1, m) scanf("%s", s + 1), io >> x, add(s, x);
build();
lf l = 0, r = n * 1e5;
while (r - l > eps) {
lf mid = (l + r) / 2;
if (ok(mid)) l = mid;
else r = mid;
}
For (i, 1, n) {
ll x = round(l * i);
if (fabs(x - l * i) < n * eps) { printf("%d\n", ml(x % Mo, qPow(i, Mo - 2))); return; }
}
}
int main() {
io >> T;
while (T--) solve();
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 101ms
memory: 32324kb
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:
92946 249620131 499198100 96670 332788889 81272 61572 67112 69859 95033 88888 199691258 74929 798635141 17290 33737 76430 60785 58076 499183986 78051 77523 499194475 332787384 95383 89874 80292 90741 499160996 41750 256056074 748759832 199727753 94537 83443 93595 499175237 332766789 62015 249621366 ...
result:
wrong answer 1st lines differ - expected: '332874949', found: '92946'