QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#415192#7632. Balanced ArrayscaijianhongAC ✓90ms47732kbC++234.9kb2024-05-20 15:37:332024-05-20 15:37:34

Judging History

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

  • [2024-05-20 15:37:34]
  • 评测
  • 测评结果:AC
  • 用时:90ms
  • 内存:47732kb
  • [2024-05-20 15:37:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
typedef long long LL;
template <class T>
using must_int = enable_if_t<is_integral<T>::value, int>;
template <unsigned umod>
struct modint { /*{{{*/
  static constexpr int mod = umod;
  unsigned v;
  modint() : v(0) {}
  template <class T, must_int<T> = 0>
    modint(T x) {
      x %= mod;
      v = x < 0 ? x + mod : x;
    }
  modint operator+() const { return *this; }
  modint operator-() const { return modint() - *this; }
  friend int raw(const modint &self) { return self.v; }
  friend ostream &operator<<(ostream &os, const modint &self) {
    return os << raw(self);
  }
  modint &operator+=(const modint &rhs) {
    v += rhs.v;
    if (v >= umod) v -= umod;
    return *this;
  }
  modint &operator-=(const modint &rhs) {
    v -= rhs.v;
    if (v >= umod) v += umod;
    return *this;
  }
  modint &operator*=(const modint &rhs) {
    v = 1ull * v * rhs.v % umod;
    return *this;
  }
  modint &operator/=(const modint &rhs) {
    assert(rhs.v);
    return *this *= qpow(rhs, mod - 2);
  }
  template <class T, must_int<T> = 0>
    friend modint qpow(modint a, T b) {
      modint r = 1;
      for (; b; b >>= 1, a *= a)
        if (b & 1) r *= a;
      return r;
    }
  friend modint operator+(modint lhs, const modint &rhs) { return lhs += rhs; }
  friend modint operator-(modint lhs, const modint &rhs) { return lhs -= rhs; }
  friend modint operator*(modint lhs, const modint &rhs) { return lhs *= rhs; }
  friend modint operator/(modint lhs, const modint &rhs) { return lhs /= rhs; }
  bool operator==(const modint &rhs) const { return v == rhs.v; }
  bool operator!=(const modint &rhs) const { return v != rhs.v; }
}; /*}}}*/
typedef modint<998244353> mint;
int glim(int n) { return 1 << (32 - __builtin_clz(n - 1)); }
int bitctz(int n) { return __builtin_ctz(n); }
template <class mint, int G>
struct NTT_env {
  vector<mint> w{1};
  void init(int n) {
    if (w.size() < n) w.reserve(n);
    while (w.size() < n) {
      int m = w.size();
      mint wn = qpow(mint(G), (mint::mod - 1) / m >> 2);
      w.resize(m << 1);
      for (int i = m; i < m << 1; i++) w[i] = wn * w[i ^ m];
    }
  }
  void dif(vector<mint> &a) {
    int n = a.size();
    init(n);
    for (int len = n, k = n >> 1; k >= 1; len = k, k >>= 1) {
      for (int i = 0, t = 0; i < n; i += len, t++) {
        for (int j = 0; j < k; j++) {
          mint x = a[i + j], y = a[i + j + k] * w[t];
          a[i + j] = x + y, a[i + j + k] = x - y;
        }
      }
    }
  }
  void dit(vector<mint> &a) {
    int n = a.size();
    init(n);
    for (int k = 1, len = 2; len <= n; k = len, len <<= 1) {
      for (int i = 0, t = 0; i < n; i += len, t++) {
        for (int j = 0; j < k; j++) {
          mint x = a[i + j], y = a[i + j + k];
          a[i + j] = x + y, a[i + j + k] = (x - y) * w[t];
        }
      }
    }
    mint iv = mint(1) / n;
    for (int i = 0; i < n; i++) a[i] *= iv;
    reverse(a.begin() + 1, a.end());
  }
};
vector<mint> convolution(vector<mint> a, vector<mint> b) {
  static NTT_env<mint, 3> ntt;
  int rlen = a.size() + b.size() - 1, len = glim(rlen);
  a.resize(len), ntt.dif(a);
  b.resize(len), ntt.dif(b);
  for (int i = 0; i < len; i++) a[i] *= b[i];
  ntt.dit(a), a.resize(rlen);
  return a;
}
template <int N>
struct C_prime { /*{{{*/
  mint fac[N + 10], ifac[N + 10];
  C_prime() {
    for (int i = raw(fac[0] = 1); i <= N; i++) fac[i] = fac[i - 1] * i;
    ifac[N] = 1 / fac[N];
    for (int i = N; i >= 1; i--) ifac[i - 1] = ifac[i] * i;
  }
  mint operator()(int n, int m) {
    return n >= m ? fac[n] * ifac[m] * ifac[n - m] : 0;
  }
}; /*}}}*/
int n, m;
C_prime<2000010> binom;
mint f[2000010], g[2000010];
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
  cin >> n >> m;
  mint ans = 1;
  while (false) {
    for (int i = 1; i <= m; i++) {
      for (int k = 1; k <= i; k++) {
        //    ans += binom(i - 1, k - 1) * binom(i, k - 1) *
        //           binom(n - 2 * k + 2 * i + 1, 2 * i) * binom.ifac[k] *
        //           binom.fac[k - 1];
        ans += binom.fac[i - 1] * binom.ifac[i - k] * binom.ifac[k - 1] *
          binom.fac[i] * binom.ifac[i - k + 1] *
          binom.fac[n - 2 * k + 2 * i + 1] * binom.ifac[2 * i] *
          binom.ifac[n - 2 * k + 1] * binom.ifac[k];
      }
    }
  }
  int lim = (n + 1) >> 1;
  // i - k
  for (int i = 0; i <= m - 1; i++) f[i] = binom.ifac[i] * binom.ifac[i + 1] * binom.fac[n + 2 * i + 1];
  // k
  for (int i = 1; i <= lim; i++) g[i] = binom.ifac[i] * binom.ifac[i - 1] * binom.ifac[n - 2 * i + 1];
  vector<mint> ret = convolution(vector<mint>(f, f + m), vector<mint>(g, g + lim + 1));
  for (int i = 1; i < ret.size() && i <= m; i++) {
    ans += binom.fac[i - 1] * binom.fac[i] * binom.ifac[2 * i] * ret[i];
    debug("i = %d, ans += %d\n", i, raw(binom.fac[i - 1] * binom.fac[i] * binom.ifac[2 * i] * ret[i]));
  }
  cout << ans << endl;
  return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 13ms
memory: 34836kb

input:

2 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 86ms
memory: 47592kb

input:

500000 500000

output:

984531374

result:

ok 1 number(s): "984531374"

Test #3:

score: 0
Accepted
time: 26ms
memory: 38504kb

input:

500000 1

output:

219705876

result:

ok 1 number(s): "219705876"

Test #4:

score: 0
Accepted
time: 50ms
memory: 40832kb

input:

1 500000

output:

500001

result:

ok 1 number(s): "500001"

Test #5:

score: 0
Accepted
time: 85ms
memory: 47664kb

input:

500000 353535

output:

33730077

result:

ok 1 number(s): "33730077"

Test #6:

score: 0
Accepted
time: 85ms
memory: 47296kb

input:

353535 500000

output:

182445298

result:

ok 1 number(s): "182445298"

Test #7:

score: 0
Accepted
time: 89ms
memory: 47656kb

input:

499999 499999

output:

933220940

result:

ok 1 number(s): "933220940"

Test #8:

score: 0
Accepted
time: 86ms
memory: 47676kb

input:

499999 499998

output:

899786345

result:

ok 1 number(s): "899786345"

Test #9:

score: 0
Accepted
time: 85ms
memory: 47484kb

input:

377773 400009

output:

206748715

result:

ok 1 number(s): "206748715"

Test #10:

score: 0
Accepted
time: 52ms
memory: 41468kb

input:

499999 100001

output:

482775773

result:

ok 1 number(s): "482775773"

Test #11:

score: 0
Accepted
time: 90ms
memory: 47620kb

input:

444445 488884

output:

70939759

result:

ok 1 number(s): "70939759"

Test #12:

score: 0
Accepted
time: 85ms
memory: 47544kb

input:

488885 444449

output:

591315327

result:

ok 1 number(s): "591315327"

Test #13:

score: 0
Accepted
time: 31ms
memory: 38576kb

input:

500000 111

output:

313439156

result:

ok 1 number(s): "313439156"

Test #14:

score: 0
Accepted
time: 86ms
memory: 47304kb

input:

333333 444444

output:

403492103

result:

ok 1 number(s): "403492103"

Test #15:

score: 0
Accepted
time: 84ms
memory: 47732kb

input:

499994 343433

output:

334451699

result:

ok 1 number(s): "334451699"

Test #16:

score: 0
Accepted
time: 90ms
memory: 47520kb

input:

477774 411113

output:

63883341

result:

ok 1 number(s): "63883341"

Test #17:

score: 0
Accepted
time: 41ms
memory: 41376kb

input:

123456 432109

output:

238795570

result:

ok 1 number(s): "238795570"

Test #18:

score: 0
Accepted
time: 85ms
memory: 46872kb

input:

131331 467777

output:

834790039

result:

ok 1 number(s): "834790039"

Test #19:

score: 0
Accepted
time: 35ms
memory: 38512kb

input:

500000 2

output:

304727284

result:

ok 1 number(s): "304727284"

Test #20:

score: 0
Accepted
time: 17ms
memory: 34872kb

input:

1111 111

output:

98321603

result:

ok 1 number(s): "98321603"

Test #21:

score: 0
Accepted
time: 86ms
memory: 47396kb

input:

416084 493105

output:

916827025

result:

ok 1 number(s): "916827025"

Test #22:

score: 0
Accepted
time: 31ms
memory: 37432kb

input:

53888 138663

output:

57263952

result:

ok 1 number(s): "57263952"

Test #23:

score: 0
Accepted
time: 41ms
memory: 41892kb

input:

219161 382743

output:

304889787

result:

ok 1 number(s): "304889787"

Test #24:

score: 0
Accepted
time: 50ms
memory: 40820kb

input:

181392 318090

output:

12528742

result:

ok 1 number(s): "12528742"

Test #25:

score: 0
Accepted
time: 54ms
memory: 40724kb

input:

135930 422947

output:

554153000

result:

ok 1 number(s): "554153000"

Test #26:

score: 0
Accepted
time: 57ms
memory: 41024kb

input:

280507 210276

output:

812816587

result:

ok 1 number(s): "812816587"

Test #27:

score: 0
Accepted
time: 83ms
memory: 47176kb

input:

253119 420465

output:

124024302

result:

ok 1 number(s): "124024302"

Test #28:

score: 0
Accepted
time: 56ms
memory: 41372kb

input:

446636 97448

output:

150388382

result:

ok 1 number(s): "150388382"

Test #29:

score: 0
Accepted
time: 52ms
memory: 41016kb

input:

284890 126665

output:

786559507

result:

ok 1 number(s): "786559507"

Test #30:

score: 0
Accepted
time: 21ms
memory: 36400kb

input:

186708 28279

output:

607509026

result:

ok 1 number(s): "607509026"

Extra Test:

score: 0
Extra Test Passed