QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#242448 | #7512. Almost Prefix Concatenation | yyz | WA | 0ms | 3744kb | C++14 | 3.4kb | 2023-11-07 14:00:57 | 2023-11-07 14:00:57 |
Judging History
answer
#include <bits/stdc++.h>
#define V vector
#define Vi vector<int>
#define sz(a) ((int)a.size())
#define fi first
#define se second
#define Int pair<int, int>
#define Inf ((int)1e9)
#define pb push_back
#define ins insert
#define For(i, x, y) for (int i = (x); i <= (y); i++)
#define Rep(i, x, y) for (int i = (x); i >= (y); i--)
#define seg int p, int l, int r
#define lid p << 1, l, mid
#define all(a) a.begin(), a.end()
#define rid p << 1 | 1, mid + 1, r
#define mid ((l + r) / 2)
#define Ceil(x, y) ((x + y - 1) / y)
#define IO(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
using namespace std;
#define ull unsigned long long
const ull B = 31;
struct Ace_taffy {
Ace_taffy(int n, string &S) : s(n + 5), pw(n + 5) {
pw[0] = 1;
For(i, 1, n) s[i] = s[i - 1] * B + S[i] - 'a' + 1, pw[i] = pw[i - 1] * B;
}
ull ask(int l, int r) { return s[r] - s[l - 1] * pw[r - l + 1]; }
V<ull> s, pw;
};
#define ll long long
const int P = 998244353;
struct mint {
int d;
mint() = default;
mint(int x) : d(x < 0 ? x + P : x) {}
mint(ll x) : d(int(x % P)) {}
explicit operator int() { return d; }
friend istream &operator>>(istream &x, mint &y) { return x >> y.d; }
friend ostream &operator<<(ostream &x, mint y) { return x << y.d; }
friend mint operator+(mint x, mint y) {
return (x.d += y.d) < P ? x.d : x.d - P;
}
mint &operator+=(mint z) { return (d += z.d) < P ? d : d -= P, *this; }
friend mint operator-(mint x, mint y) {
return (x.d -= y.d) < 0 ? x.d + P : x.d;
}
mint &operator-=(mint z) { return (d -= z.d) < 0 ? d += P : d, *this; }
friend mint operator*(mint x, mint y) { return int(1ll * x.d * y.d % P); }
mint &operator*=(mint z) { return d = int(1ll * d * z.d % P), *this; }
static mint qpow(int x, ll y = P - 2) {
int z = 1;
for (; y; y >>= 1, x = int(1ll * x * x % P))
if (y & 1) z = int(1ll * x * z % P);
return z;
}
friend mint operator/(mint x, mint y) { return x *= qpow(y.d); }
mint &operator/=(mint z) { return (*this) *= qpow(z.d); }
mint inv() { return qpow(d); }
mint pow(mint z) { return qpow(d, z.d); }
mint pow(int z) { return z >= 0 ? qpow(d, z) : 1 / qpow(d, -z); }
mint operator+() { return d; }
mint operator-() { return P - d; }
};
mint operator""_m(unsigned ll x) { return mint(int(x)); }
int main() {
#ifndef ONLINE_JUDGE
IO(1);
#endif
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
string S, T;
cin >> S >> T;
int n = sz(S), m = sz(T);
S = " " + S, T = " " + T;
Ace_taffy sa(n, S), sb(m, T);
auto jump = [&](int x, int y) {
int l = 0, r = min(n - x + 1, m - y + 1), ans = 0;
while (l <= r) {
if (sa.ask(x, x + mid - 1) == sb.ask(y, y + mid - 1))
ans = mid, l = mid + 1;
else
r = mid - 1;
}
return y + ans - 1;
};
V<mint> f0(n + 5), f1(n + 5), f2(n + 5), s0(n + 5), s1(n + 5), s2(n + 5);
f0[0] = 1;
For(i, 1, n) {
int t = jump(i, 1);
if (t == m - 1 || t == n - i) t++;
if (t < m && t < n - i + 1) t = jump(i + t + 1, t + 2);
s0[i] += f0[i - 1], s0[i + t] -= f0[i - 1];
s1[i] += f1[i - 1] + f0[i - 1], s1[i + t] -= f1[i - 1] + f0[i - 1];
s2[i] += f2[i - 1] + 2 * f1[i - 1] + f0[i - 1];
s2[i + t] -= f2[i - 1] + 2 * f1[i - 1] + f0[i - 1];
s0[i] += s0[i - 1], s1[i] += s1[i - 1], s2[i] += s2[i - 1];
f0[i] = s0[i], f1[i] = s1[i], f2[i] = s2[i];
}
cout << f2[n] << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3744kb
input:
ababaab aba
output:
473
result:
ok 1 number(s): "473"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
ac ccpc
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3576kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
495807373
result:
wrong answer 1st numbers differ - expected: '75038697', found: '495807373'