QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#180737#6513. Expression 3ClHg2TL 2684ms74856kbC++147.4kb2023-09-16 11:02:122023-09-16 11:02:13

Judging History

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

  • [2024-02-14 13:23:19]
  • hack成功,自动添加数据
  • (/hack/531)
  • [2023-09-16 11:02:13]
  • 评测
  • 测评结果:TL
  • 用时:2684ms
  • 内存:74856kb
  • [2023-09-16 11:02:12]
  • 提交

answer

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

namespace {
using std::cin;
using std::cout;
using std::int64_t;
using int128_t = __int128;

const int kP = 998244353, kInv2 = (kP + 1) / 2, kG = 3, kInvG = 332748118;

namespace mod {
inline int Mod(int x) { return x >= kP ? x - kP : x; }
inline void Add(int& x, int y) { x = Mod(x + y); }
inline int Fix(int x) { return x + (x >> 31 & kP); }
inline void Sub(int& x, int y) { x = Fix(x - y); }
inline int Unm(int x) { return x ? kP - x : x; }
inline void Neg(int& x) { x = Unm(x); }

int64_t Pow(int64_t a, int b) {
  int64_t ans = 1;

  while (b) {
    if (b & 1) ans = ans * a % kP;
    a = a * a % kP, b >>= 1;
  }

  return ans;
}

inline int64_t Inv(int64_t a) { return Pow(a, kP - 2); }
}  // namespace mod

namespace poly {
inline int Ceil(int n) {
  if (n == 1) return 1;
  return 1 << (32 - __builtin_clz(n - 1));
}

struct Poly {
  std::vector<int> c;
  int Size() const { return c.size(); }
  void Resize(int n) { c.resize(n); }
  void Reverse() { std::reverse(c.begin(), c.end()); }
  int operator[](int i) const { return c[i]; }
  int& operator[](int i) { return c[i]; }
};

Poly& operator+=(Poly& f, const Poly& g) {
  int n = f.Size(), m = g.Size(), len = std::max(n, m);
  f.Resize(len);
  for (int i = 0; i < m; ++i) mod::Add(f[i], g[i]);
  return f;
}

Poly operator+(Poly f, const Poly& g) { return f += g; }

Poly& operator-=(Poly& f, const Poly& g) {
  int n = f.Size(), m = g.Size(), len = std::max(n, m);
  f.Resize(len);
  for (int i = 0; i < m; ++i) mod::Sub(f[i], g[i]);
  return f;
}

Poly operator-(Poly f, const Poly& g) { return f -= g; }

Poly operator-(Poly f) {
  int n = f.Size();
  for (int i = 0; i < n; ++i) mod::Neg(f[i]);
  return f;
}

Poly& operator*=(Poly& f, int64_t k) {
  int n = f.Size();
  for (int i = 0; i < n; ++i) f[i] = f[i] * k % kP;
  return f;
}

Poly operator*(Poly f, int64_t k) { return f *= k; }

Poly rev;

void InitRev(int n) {
  int m = rev.Size();
  if (m == n) return;
  rev.Resize(n);
  int e = __builtin_ctz(n);

  for (int i = 1; i < n; ++i) {
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (e - 1));
  }
}

Poly w = {{0}};

void InitW(int n, int g) {
  int m = w.Size();
  if (m == n && w[0] == g) return;
  w[0] = g, w.Resize(n);

  for (int i = 1; i < n; i <<= 1) {
    int64_t w_i = mod::Pow(g, (kP - 1) / (i << 1)), w_i_j = 1;
    for (int j = 0; j < i; ++j) w[i | j] = w_i_j, w_i_j = w_i_j * w_i % kP;
  }
}

void Ntt(Poly& f, int type) {
  int n = f.Size();
  InitRev(n);
  InitW(n, type == 1 ? kG : kInvG);

  for (int i = 0; i < n; ++i) {
    if (i < rev[i]) std::swap(f[i], f[rev[i]]);
  }

  for (int i = 1; i < n; i <<= 1) {
    for (int j = 0; j < n; j += (i << 1)) {
      for (int k = 0; k < i; ++k) {
        int x = f[j | k], y = int64_t{f[i | j | k]} * w[i | k] % kP;
        f[j | k] = mod::Mod(x + y), f[i | j | k] = mod::Fix(x - y);
      }
    }
  }

  if (type == -1) {
    int64_t inv = mod::Inv(n);
    for (int i = 0; i < n; ++i) f[i] = f[i] * inv % kP;
  }
}

Poly& operator*=(Poly& f, Poly g) {
  int n = f.Size(), m = g.Size(), len = Ceil(n + m - 1);
  f.Resize(len), g.Resize(len);
  Ntt(f, 1), Ntt(g, 1);
  for (int i = 0; i < len; ++i) f[i] = int64_t{f[i]} * g[i] % kP;
  Ntt(f, -1);
  f.Resize(n + m - 1);
  return f;
}

Poly operator*(Poly f, const Poly& g) { return f *= g; }

Poly Slice(const Poly& f, int l, int r) {
  Poly g;
  g.Resize(r - l + 1);
  for (int i = 0; i <= r - l; ++i) g[i] = f[i + l];
  return g;
}

Poly Inv(Poly f) {
  int n = f.Size(), len = Ceil(n);
  f.Resize(len);
  Poly g = {{static_cast<int>(mod::Inv(f[0]))}};

  for (int w = 2; w <= len; w <<= 1) {
    g = g * 2 - g * g * Slice(f, 0, w - 1);
    g.Resize(w);
  }

  g.Resize(n);
  return g;
}

Poly& operator/=(Poly& f, Poly g) {
  int n = f.Size(), m = g.Size(), len = n - m + 1;
  f.Reverse(), g.Reverse();
  f.Resize(len), g.Resize(len);
  f *= Inv(g);
  f.Resize(len), f.Reverse();
  return f;
}

Poly operator/(Poly f, const Poly& g) { return f /= g; }

Poly Sqrt(Poly f) {
  int n = f.Size(), len = Ceil(n);
  f.Resize(len);
  Poly g = {{1}};

  for (int w = 2; w <= len; w <<= 1) {
    Poly h = g;
    h.Resize(w);
    g = (g * g + Slice(f, 0, w - 1)) * Inv(h) * kInv2;
    g.Resize(w);
  }

  g.Resize(n);
  if (g[0] * 2 > kP) return -g;
  return g;
}

Poly Derivative(const Poly& f) {
  int n = f.Size();
  if (n == 1) return {{0}};
  Poly g;
  g.Resize(n - 1);
  for (int i = 0; i < n - 1; ++i) g[i] = int64_t{f[i + 1]} * (i + 1) % kP;
  return g;
}

Poly inv = {{0, 1}};

void InitInv(int n) {
  int m = inv.Size();
  if (m - 1 >= n) return;
  inv.Resize(n + 1);

  for (int i = m; i <= n; ++i) {
    inv[i] = int64_t{inv[kP % i]} * (kP - kP / i) % kP;
  }
}

Poly Integration(const Poly& f) {
  int n = f.Size();
  InitInv(n);
  Poly g;
  g.Resize(n + 1), g[0] = 0;
  for (int i = 1; i <= n; ++i) g[i] = int64_t{f[i - 1]} * inv[i] % kP;
  return g;
}

Poly Ln(const Poly& f) {
  int n = f.Size();
  Poly g = Integration(Derivative(f) * Inv(f));
  g.Resize(n);
  return g;
}

Poly Exp(Poly f) {
  int n = f.Size(), len = Ceil(n);
  f.Resize(len);
  Poly g = {{1}};

  for (int w = 2; w <= len; w <<= 1) {
    Poly h = g;
    h.Resize(w);
    g -= (Ln(h) - Slice(f, 0, w - 1)) * g;
    g.Resize(w);
  }

  g.Resize(n);
  return g;
}

Poly Pow(Poly f, int k) {
  int n = f.Size(), p = 0;
  while (p < n && f[p] == 0) ++p;
  if (p == n) return f;
  int x = f[p];
  f = Slice(f, p, n - 1) * mod::Inv(x);
  f = Exp(Ln(f) * k);
  Poly g;
  g.Resize(n);
  for (int i = p * k; i < n; ++i) g[i] = f[i - p * k];
  return g * mod::Pow(x, k);
}
}  // namespace poly

using poly::Poly;

const int kMaxN = 2.0e5 + 5, kMax4N = kMaxN * 4;
int n;
int fac[kMaxN], inv_fac[kMaxN], a[kMaxN], b[kMaxN], c[kMaxN];
std::string str;
Poly f[kMax4N], g[kMax4N];

void InitChoose() {
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = int64_t{fac[i - 1]} * i % kP;
  inv_fac[n] = mod::Inv(fac[n]);
  for (int i = n; i >= 1; --i) inv_fac[i - 1] = int64_t{inv_fac[i]} * i % kP;
}

#define LC p << 1
#define RC (p << 1 | 1)

void Build(int p, int l, int r) {
  if (l == r) {
    f[p] = {{c[l], 1}}, g[p] = {{kP - l, 1}};
    return;
  }

  int mid = (l + r) >> 1;
  Build(LC, l, mid), Build(RC, mid + 1, r);
  f[p] = f[LC] * f[RC], g[p] = g[LC] * g[RC];
}

void Solve(int p, int l, int r, Poly h) {
  if (h.Size() >= g[p].Size()) {
    h -= h / g[p] * g[p];
    while (!h.c.empty() && h.c.back() == 0) h.c.pop_back();
  }

  if (l == r) {
    b[l] = (h.c.empty() ? 0 : h[0]);
    return;
  }

  int mid = (l + r) >> 1;
  Solve(LC, l, mid, h), Solve(RC, mid + 1, r, h * f[LC]);
}

#undef LC
#undef RC
}  // namespace

int main() {
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> a[i];
  cin >> str, str = std::string(" ").append(str);
  for (int i = 1; i < n; ++i) c[i] = mod::Fix((str[i] == '+' ? 1 : -1) - i);
  InitChoose();
  Build(1, 1, n - 1);
  Solve(1, 1, n - 1, Poly({{1}}));
  int128_t ans = a[0];

  for (int i = 1; i < n; ++i) {
    int64_t val = int64_t{a[i]} * b[i] % kP * inv_fac[i];
    ans += (str[i] == '+' ? val : -val);
  }

  cout << mod::Fix(ans % kP * fac[n - 1] % kP) << "\n";
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 44740kb

input:

4
9 1 4 1
-+-

output:

46

result:

ok 1 number(s): "46"

Test #2:

score: 0
Accepted
time: 3ms
memory: 44136kb

input:

5
1 2 3 4 5
+-+-

output:

998244313

result:

ok 1 number(s): "998244313"

Test #3:

score: 0
Accepted
time: 2684ms
memory: 74856kb

input:

100000
664815434 205025136 871445392 797947979 379688564 336946672 231295524 401655676 526374414 670533644 156882283 372427821 700299596 166140732 677498490 44858761 185182210 559696133 813911251 842364231 681916958 114039865 222372111 784286397 437994571 152137641 650875922 613727135 209302742 5321...

output:

178167352

result:

ok 1 number(s): "178167352"

Test #4:

score: -100
Time Limit Exceeded

input:

200000
109044620 745578941 396599814 756923982 940933214 875346257 378089839 792684563 491924893 782192923 208569108 421583135 814903710 690275542 15773609 364566266 12890134 661702679 640270667 615999192 13352194 325560419 385152885 265008089 570536451 282429805 331946208 255056541 813809151 150995...

output:


result: