QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#242457#7512. Almost Prefix ConcatenationyyzWA 0ms3776kbC++143.4kb2023-11-07 14:11:222023-11-07 14:11:23

Judging History

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

  • [2023-11-07 14:11:23]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3776kb
  • [2023-11-07 14:11:22]
  • 提交

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 = 131;
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';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3776kb

input:

ababaab
aba

output:

473

result:

ok 1 number(s): "473"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

ac
ccpc

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3624kb

input:

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...

output:

495807373

result:

wrong answer 1st numbers differ - expected: '75038697', found: '495807373'