QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#867084#9777. Balance in All Thingsnhuang685AC ✓4848ms732044kbC++239.1kb2025-01-23 03:58:342025-01-23 03:58:34

Judging History

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

  • [2025-01-23 03:58:34]
  • 评测
  • 测评结果:AC
  • 用时:4848ms
  • 内存:732044kb
  • [2025-01-23 03:58:34]
  • 提交

answer

/**
 * @author n685
 * @date 2025-01-21 16:50:08
 */
#include "bits/stdc++.h"

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif

namespace rs = std::ranges;
namespace rv = std::views;

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

namespace modular {

// from tourist
template <std::integral T> T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a;
    std::swap(a, m);
    u -= t * v;
    std::swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <class Md, class V = long long>
  requires std::signed_integral<std::decay_t<decltype(Md::value)>>
struct Mod {
  using T = std::decay_t<decltype(Md::value)>;
  T val = 0;

  static constexpr T normalize(std::integral auto val) {
    using U = decltype(Md::value + val);
    U uval = static_cast<U>(val);
    U umd = static_cast<U>(Md::value);
    if (uval <= -umd || umd <= uval) {
      uval %= umd;
    }
    if (val < 0) {
      uval += umd;
    }
    return static_cast<T>(uval);
  }
  constexpr Mod() : val(0) {}
  constexpr explicit Mod(std::integral auto _val) : val(normalize(_val)) {}

  // addition
  constexpr Mod& operator+=(Mod b) {
    val += b.val;
    if (val >= Md::value) {
      val -= Md::value;
    }
    return *this;
  }
  friend constexpr Mod operator+(Mod a, Mod b) { return a += b; }
  constexpr Mod& operator++() { return *this += Mod{1}; }
  constexpr Mod operator++(int) {
    Mod res = *this;
    ++(*this);
    return res;
  }

  // subtraction
  constexpr Mod& operator-=(Mod b) {
    val -= b.val;
    if (val < 0) {
      val += Md::value;
    }
    return *this;
  }
  friend constexpr Mod operator-(Mod a, Mod b) { return a -= b; }
  constexpr Mod& operator--() { return *this -= Mod{1}; }
  constexpr Mod operator--(int) {
    Mod res = *this;
    --(*this);
    return res;
  }
  // negation
  constexpr Mod operator-() const { return Mod{-val}; }

  // multiplication
  constexpr Mod& operator*=(Mod b) {
    val = static_cast<T>(static_cast<V>(val) * b.val % Md::value);
    return *this;
  }
  friend constexpr Mod operator*(Mod a, Mod b) { return a *= b; }
  constexpr Mod binpow(std::integral auto b) const {
    Mod res{1}, a = *this;
    while (b > 0) {
      if (b % 2 == 1) {
        res *= a;
      }
      a *= a;
      b /= 2;
    }
    return res;
  }

  // factorial
  // align with fft, if code fails to compile make this smaller (if using array)
  static constexpr int MXINV = 1 << 22;
  static inline bool init = false;
  static inline std::vector<Mod> ff, iff;
  static void reset_fac() { init = false; }
  static void init_fac() {
    if (init) {
      return;
    }
    ff.resize(MXINV + 1);
    ff[0] = Mod{1};
    for (int i = 1; i <= MXINV; ++i) {
      ff[i] = ff[i - 1] * Mod{i};
    }
    iff.resize(MXINV + 1);
    iff[MXINV] = ff[MXINV].large_inv();
    for (int i = MXINV - 1; i >= 0; --i) {
      iff[i] = iff[i + 1] * Mod{i + 1};
    }
    init = true;
  }
  static Mod fac(int v) {
    if (!init) {
      init_fac();
    }
    return ff[v];
  }
  static Mod ifac(int v) {
    if (!init) {
      init_fac();
    }
    return iff[v];
  }
  static Mod comb(int n, int k) {
    if (n < 0 || k < 0 || n < k) {
      return Mod{0};
    }
    return fac(n) * ifac(n - k) * ifac(k);
  }
  static Mod perm(int n, int k) {
    if (n < 0 || k < 0 || n < k) {
      return Mod{0};
    }
    return fac(n) * ifac(n - k);
  }

  // inverse
  Mod small_inv() const {
    return ifac(static_cast<int>(val)) * fac(static_cast<int>(val) - 1);
  }
  constexpr Mod large_inv() const {
    return Mod{inverse(val, Md::value)};
    // return binpow(Md::value - 2);
  }
  Mod inv() const {
    if (val <= MXINV) {
      return small_inv();
    }
    return large_inv();
  }

  // sqrt
  std::optional<Mod> sqrt() {
    static std::mt19937_64 rng(
      std::chrono::steady_clock::now().time_since_epoch().count());
    Mod c{0};
    while ((c * c - *this).binpow((Md::value - 1) / 2) == Mod{1}) {
      c = Mod{rng()};
    }
    if (c == Mod{0}) {
      return std::nullopt;
    }
    std::pair<Mod, Mod> res(Mod{1}, Mod{0}), a(c, Mod{1});
    T b = (Md::value + 1) / 2;
    auto mul = [&c, this](const std::pair<Mod, Mod>& u,
                 const std::pair<Mod, Mod>& v) -> std::pair<Mod, Mod> {
      return {u.first * v.first + u.second * v.second * (c * c - *this),
        u.second * v.first + u.first * v.second};
    };
    while (b > 0) {
      if (b % 2 == 1) {
        res = mul(res, a);
      }
      a = mul(a, a);
      b /= 2;
    }
    return res.first;
    // return std::min(res.first, -res.first);
  }

  // comparison
  constexpr bool operator==(const Mod& b) const = default;
  constexpr std::strong_ordering operator<=>(const Mod& b) const = default;

  // io
  friend std::istream& operator>>(std::istream& in, Mod& a) {
    long long v;
    in >> v;
    a = Mod{v};
    return in;
  }
  friend std::ostream& operator<<(std::ostream& out, const Mod& a) {
    out << a.val;
    return out;
  }

  // conversion
  constexpr T value() const { return val; }
};

} // namespace modular

#if defined(LOCAL) && __cplusplus >= 202302L
template <class Md, class V>
  requires std::formattable<typename modular::Mod<Md, V>::T, char>
struct std::formatter<modular::Mod<Md, V>, char> {
  using T = typename modular::Mod<Md, V>::T;
  std::formatter<T, char> underlying;
  constexpr formatter() {
    if constexpr (requires { underlying.set_debug_format(); }) {
      underlying.set_debug_format();
    }
  }
  template <class ParseContext> constexpr auto parse(ParseContext& ctx) {
    return underlying.parse(ctx);
  }
  template <class FormatContext>
  auto format(const modular::Mod<Md, V>& val, FormatContext& ctx) const {
    return underlying.format(val.value(), ctx);
  }
};
#endif

struct Md {
  static inline int value;
};
using Mint = modular::Mod<Md>;

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int n, k;
  std::cin >> n >> k >> Md::value;

  std::vector<std::vector<std::vector<Mint>>> f(2 * n + 1);
  f[0].resize(2 * n + 1);
  for (int b = 0; b <= 2 * n; ++b) {
    f[0][b].resize((2 * n - b) + 1);
    if (b + b <= 2 * n) {
      f[0][b][b] = Mint::fac(b);
    }
  }
  for (int a = 1; a <= 2 * n; ++a) {
    f[a].resize((2 * n - a) + 1);
    for (int b = 0; a + b <= 2 * n; ++b) {
      f[a][b].resize((2 * n - a - b) + 1);
      for (int c = 0; a + b + c <= 2 * n; ++c) {
        if (a >= 2) {
          f[a][b][c] += Mint{a - 1} * f[a - 2][b][c];
        }
        if (b >= 1) {
          f[a][b][c] += Mint{b} * f[a - 1][b - 1][c];
        }
        if (c >= 1) {
          f[a][b][c] += Mint{c} * f[a - 1][b][c - 1];
        }
      }
    }
  }

  std::vector<std::vector<std::vector<Mint>>> g(2 * n + 1);
  // for convenience
  g[0].resize(2 * n + 1);
  for (int b = 0; b <= 2 * n; ++b) {
    g[0][b].resize(b / 2 + 1);
    g[0][b][0] = Mint{1};
  }
  for (int a = 1; a <= 2 * n; ++a) {
    g[a].resize((2 * n - a) + 1);
    for (int b = 0; (a + b) <= 2 * n; ++b) {
      g[a][b].resize((a + b) / 2 + 1);
      g[a][b][0] = Mint{1};
      for (int c = 1; c <= (a + b) / 2; ++c) {
        if (((a - 1) + b) / 2 >= c) {
          g[a][b][c] = g[a - 1][b][c];
        }
        if (a >= 2) {
          g[a][b][c] += Mint{a - 1} * g[a - 2][b][c - 1];
        }
        if (b >= 1) {
          g[a][b][c] += Mint{b} * g[a - 1][b - 1][c - 1];
        }
      }
    }
  }

  std::vector<Mint> h(2 * n + 1);
  h[0] = Mint{1};
  for (int i = 2; i <= 2 * n; i += 2) {
    h[i] = Mint{i - 1} * h[i - 2];    
  }
  dbg(h);

  std::vector<Mint> even(n + 1);
  std::vector odd(n + 1, std::vector<Mint>(n + 1));
  even[0] = Mint{1};
  for (int t = 1; t <= k; ++t) {
    if (t % 2 == 1) {
      for (int j = 0; j <= n / 2; ++j) {
        for (int kk = 0; kk <= n / 2; ++kk) {
          odd[j][kk] = Mint{0};
          for (int i = std::max(2 * j, 2 * kk); i <= n; ++i) {
            odd[j][kk] += (Mint::comb(i, 2 * j) * h[2 * j]) *
              (Mint::comb(i, 2 * kk) * h[2 * kk]) *
              f[2 * (n - i)][i - 2 * j][i - 2 * kk] * even[i];
          }
        }
      }
    } else {
      for (int i = 0; i <= n; ++i) {
        even[i] = Mint{0};
        for (int j = 0; j <= std::min(n / 2, i); ++j) {
          for (int kk = 0; kk <= std::min(n / 2, i); ++kk) {
            if (n + j + kk - 2 * i >= 0) {
              int nl = n + kk - j;
              int nr = n + j - kk;
              even[i] += g[nl - j][j][i - j] * g[nr - kk][kk][i - kk] *
                Mint::fac(n + j + kk - 2 * i) * odd[j][kk];
            }
          }
        }
      }
    }
  }
  Mint ans{0};
  if (k % 2 == 0) {
    for (Mint v : even) {
      ans += v;
    }
  } else {
    for (auto& arr : odd) {
      for (Mint v : arr) {
        ans += v;
      }
    }
  }
  std::cout << ans << '\n';
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 56ms
memory: 36068kb

input:

3 1 1000000007

output:

15

result:

ok single line: '15'

Test #2:

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

input:

100 3 1000000007

output:

894710378

result:

ok single line: '894710378'

Test #3:

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

input:

6 6 1000000007

output:

103387851

result:

ok single line: '103387851'

Test #4:

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

input:

2 6 998244353

output:

729

result:

ok single line: '729'

Test #5:

score: 0
Accepted
time: 4848ms
memory: 731920kb

input:

400 20 713862469

output:

561801910

result:

ok single line: '561801910'

Test #6:

score: 0
Accepted
time: 4203ms
memory: 716500kb

input:

397 17 861815723

output:

764050494

result:

ok single line: '764050494'

Test #7:

score: 0
Accepted
time: 3575ms
memory: 686704kb

input:

391 14 189546607

output:

131011086

result:

ok single line: '131011086'

Test #8:

score: 0
Accepted
time: 2890ms
memory: 643460kb

input:

382 11 922402597

output:

58290636

result:

ok single line: '58290636'

Test #9:

score: 0
Accepted
time: 2260ms
memory: 588680kb

input:

370 8 911997731

output:

823449745

result:

ok single line: '823449745'

Test #10:

score: 0
Accepted
time: 1636ms
memory: 525192kb

input:

355 5 708230279

output:

173013324

result:

ok single line: '173013324'

Test #11:

score: 0
Accepted
time: 2754ms
memory: 455556kb

input:

337 19 742344989

output:

592413780

result:

ok single line: '592413780'

Test #12:

score: 0
Accepted
time: 2413ms
memory: 444552kb

input:

334 16 816423319

output:

567577272

result:

ok single line: '567577272'

Test #13:

score: 0
Accepted
time: 2015ms
memory: 423428kb

input:

328 13 463459417

output:

77314092

result:

ok single line: '77314092'

Test #14:

score: 0
Accepted
time: 1595ms
memory: 392960kb

input:

319 10 469180903

output:

94351928

result:

ok single line: '94351928'

Test #15:

score: 0
Accepted
time: 1211ms
memory: 354692kb

input:

307 7 240226001

output:

147458009

result:

ok single line: '147458009'

Test #16:

score: 0
Accepted
time: 881ms
memory: 311168kb

input:

292 4 725635439

output:

275908993

result:

ok single line: '275908993'

Test #17:

score: 0
Accepted
time: 1442ms
memory: 264192kb

input:

274 18 518962097

output:

200937333

result:

ok single line: '200937333'

Test #18:

score: 0
Accepted
time: 1223ms
memory: 256900kb

input:

271 15 765905797

output:

683367155

result:

ok single line: '683367155'

Test #19:

score: 0
Accepted
time: 1015ms
memory: 242564kb

input:

265 12 240076537

output:

6822852

result:

ok single line: '6822852'

Test #20:

score: 0
Accepted
time: 803ms
memory: 222848kb

input:

256 9 319057337

output:

9076486

result:

ok single line: '9076486'

Test #21:

score: 0
Accepted
time: 574ms
memory: 198396kb

input:

244 6 257631131

output:

53842743

result:

ok single line: '53842743'

Test #22:

score: 0
Accepted
time: 415ms
memory: 170876kb

input:

229 3 953863681

output:

247424565

result:

ok single line: '247424565'

Test #23:

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

input:

1 20 998244353

output:

1

result:

ok single line: '1'

Test #24:

score: 0
Accepted
time: 58ms
memory: 36200kb

input:

8 4 998244353

output:

740255777

result:

ok single line: '740255777'

Test #25:

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

input:

5 20 998244353

output:

725931122

result:

ok single line: '725931122'

Test #26:

score: 0
Accepted
time: 1693ms
memory: 732044kb

input:

400 1 1000000007

output:

705610633

result:

ok single line: '705610633'

Test #27:

score: 0
Accepted
time: 1843ms
memory: 732000kb

input:

400 2 1000000007

output:

917456162

result:

ok single line: '917456162'

Test #28:

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

input:

1 1 1000000007

output:

1

result:

ok single line: '1'

Extra Test:

score: 0
Extra Test Passed