QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91114#4903. 细菌HgCl215 332ms63096kbC++145.2kb2023-03-27 12:57:232023-03-27 12:57:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-27 12:57:37]
  • 评测
  • 测评结果:15
  • 用时:332ms
  • 内存:63096kb
  • [2023-03-27 12:57:23]
  • 提交

answer

#include <bits/stdc++.h>

template <typename T, size_t ...sizes>
struct NestedArray {};

template <typename T, size_t size, size_t ...sizes>
struct NestedArray<T, size, sizes...> {
  using Type = std::array<typename NestedArray<T, sizes...>::Type, size>;
};

template <typename T>
struct NestedArray<T> {
  using Type = T;
};

template <typename T, size_t ...sizes>
using Array = typename NestedArray<T, sizes...>::Type;

void OptimizeIO() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
}

void OptimizeIO(const std::string &input_file, const std::string &output_file) {
  static std::ifstream input_stream(input_file);
  static std::ofstream output_stream(output_file);
  std::cin.rdbuf(input_stream.rdbuf());
  std::cout.rdbuf(output_stream.rdbuf());
  std::cin.tie(nullptr), std::cout.tie(nullptr);
}

const int kMaxN = 1 << 19;
const int kMaxD = 1.2e5 + 5, kMax18D = kMaxD * 18;
const int kMod = 998244353, kG = 3;
const int kInv2 = (kMod + 1) / 2, kInvG = (kMod + 1) / 3;
int d, n, m, k, a, b, c, q, block_len, lim;
Array<int, kMaxD> fac, inv_fac;
Array<int, kMaxN> rev, f, g, h;

struct Query {
  int n, m, type, coef, pos, block_n;
  Query(): n(0), m(0), type(0), coef(0), pos(0), block_n(0) {}

  Query(int n, int m, int type, int coef, int pos):
    n(n), m(m), type(type), coef(coef), pos(pos) {
    block_n = (n - 1) / block_len + 1;
  }
};

inline bool operator<(const Query &a, const Query &b) {
  if (a.block_n != b.block_n) return a.block_n < b.block_n;
  return (a.block_n & 1 ? a.m < b.m : a.m > b.m);
}

Array<Query, kMax18D> query;

inline void Add(int &a, int b) {
  a += b;
  if (a >= kMod) a -= kMod;
}

inline int Sum(int a, int b) {
  a += b;
  if (a >= kMod) a -= kMod;
  return a;
}

inline void Sub(int &a, int b) {
  a -= b;
  if (a < 0) a += kMod;
}

inline int Dif(int a, int b) {
  a -= b;
  if (a < 0) a += kMod;
  return a;
}

inline int Unm(int a) { return a ? kMod - a : a; }

inline void Mul(int &a, int b) {
  a = static_cast<int64_t>(a) * b % kMod;
}

inline int Prod(int a, int b) {
  return static_cast<int64_t>(a) * b % kMod;
}

inline int Prod(std::initializer_list<int> list) {
  return std::accumulate(list.begin(), list.end(), static_cast<int64_t>(1),
                         [](int64_t prod, int x) { return prod * x % kMod; });
}

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

  while (b) {
    if (b & 1) Mul(ans, prod);
    Mul(prod, prod), b >>= 1;
  }

  return ans;
}

inline int Inv(int a) {
  return Pow(a, kMod - 2);
}

void Init() {
  fac[0] = 1;
  for (int i = 1; i <= d; i++) fac[i] = Prod(fac[i - 1], i);
  inv_fac[d] = Inv(fac[d]);
  for (int i = d; i >= 1; i--) inv_fac[i - 1] = Prod(inv_fac[i], i);
}

inline int Choose(int n, int m) {
  if (n < m) return 0;
  return Prod({fac[n], inv_fac[m], inv_fac[n - m]});
}

inline void F(int a, int b, int d, int type, int coef) {
  if (b < 0) return;
  query[++q] = Query(d, std::min(b, d), type, coef, d);
  if (a > 0) query[++q] = Query(d, a - 1, type, Unm(coef), d);
}

inline void F(int a, int b, int x, int d, int type, int coef) {
  F(((d - a + 1) >> 1) + x, ((d + b) >> 1) + x, d, type, coef);
}

inline void G(int a, int b, int d, int type) {
  F(a, b, 0, d, type, inv_fac[d]);
  F(a, b, a + 1, d, type, Unm(inv_fac[d]));
  F(a, b, -b - 1, d, type, Unm(inv_fac[d]));
}

void GetEgf(int a, int b, int type) {
  for (int i = 0; i <= d; i++) G(a, b, i, type);
}

void AnswerQuery() {
  std::sort(query.begin() + 1, query.begin() + q + 1);
  int n = 0, m = 0, sum = 1;

  for (int i = 1; i <= q; i++) {
    while (n > query[i].n) sum = Prod(Sum(sum, Choose(n - 1, m)), kInv2), n--;
    while (n < query[i].n) sum = Dif(Sum(sum, sum), Choose(n, m)), n++;
    while (m < query[i].m) Add(sum, Choose(n, ++m));
    while (m > query[i].m) Sub(sum, Choose(n, m--));
    int val = Prod(sum, query[i].coef);
    Add((query[i].type == 1 ? f : query[i].type == 2 ? g : h)[query[i].pos], val);
  }
}

void GetRev() {
  for (int i = 0; i < (1 << lim); i++) {
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lim - 1));
  }
}

void Ntt(Array<int, kMaxN> &f, int type) {
  for (int i = 0; i < (1 << lim); i++) {
    if (i < rev[i]) std::swap(f[i], f[rev[i]]);
  }

  for (int i = 1; i < (1 << lim); i <<= 1) {
    int w_n = Pow(type == 1 ? kG : kInvG, (kMod - 1) / (i << 1));

    for (int j = 0; j < (1 << lim); j += (i << 1)) {
      int w_n_k = 1;

      for (int k = 0; k < i; k++) {
        int x = f[j | k], y = Prod(f[i | j | k], w_n_k);
        f[j | k] = Sum(x, y), f[i | j | k] = Dif(x, y);
        Mul(w_n_k, w_n);
      }
    }
  }

  if (type == -1) {
    int inv_n = Inv(1 << lim);
    for (int i = 0; i < (1 << lim); i++) Mul(f[i], inv_n);
  }
}

int main() {
  OptimizeIO();
  std::cin >> d >> n >> m >> k >> a >> b >> c;
  n--, m--, k--, a--, b--, c--;
  Init();
  block_len = std::sqrt(n);
  GetEgf(a, n - a, 1);
  GetEgf(b, m - b, 2);
  GetEgf(c, k - c, 3);
  AnswerQuery();
  while ((1 << lim) <= d * 3) lim++;
  GetRev();
  Ntt(f, 1);
  Ntt(g, 1);
  Ntt(h, 1);
  for (int i = 0; i < (1 << lim); i++) Mul(f[i], Prod(g[i], h[i]));
  Ntt(f, -1);
  std::cout << Prod(f[d], fac[d]) << "\n";
  return 0;
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 3ms
memory: 53996kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

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

input:

50 49 44 48 49 15 25

output:

544847893

result:

ok 1 number(s): "544847893"

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #3:

score: 10
Accepted
time: 16ms
memory: 54356kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 7ms
memory: 54328kb

input:

5000 4994 4997 4994 4399 1826 1332

output:

65414465

result:

ok 1 number(s): "65414465"

Subtask #3:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 310ms
memory: 63096kb

input:

120000 300 1 1 141 1 1

output:

765131153

result:

wrong answer 1st numbers differ - expected: '637174', found: '765131153'

Subtask #4:

score: 0
Wrong Answer

Test #8:

score: 0
Wrong Answer
time: 332ms
memory: 63040kb

input:

119000 119991 119991 1 23819 52139 1

output:

261942978

result:

wrong answer 1st numbers differ - expected: '944500934', found: '261942978'

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #3:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%