QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#532663#9111. Zayin and StringZYLZPPWA 101ms32324kbC++202.7kb2024-08-25 08:24:462024-08-25 08:24:47

Judging History

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

  • [2024-08-25 08:24:47]
  • 评测
  • 测评结果:WA
  • 用时:101ms
  • 内存:32324kb
  • [2024-08-25 08:24:46]
  • 提交

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'