#1117914 (C++23) No.1655 123 Swaps

• 問題: No.1655 123 Swaps
• ユーザー: ir5
• 提出日時: 2025-09-06 00:06:02
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 248 ms / 2,000 ms
• コード長: 6,808 bytes
• コンパイル時間: 4,124 ms
• コンパイル使用メモリ: 205,940 KB
• 実行使用メモリ: 26,680 KB
• 最終ジャッジ日時: 2025-09-06 00:06:20
• 合計ジャッジ時間: 9,231 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 42

ソースコード

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <functional>
#include <iomanip>
#include <ranges>
#include <atcoder/convolution>
using namespace std;
using ll = long long;

template<typename T> auto range(T s, T e) { return views::iota(s, max(s, e)); }
template<typename T> auto range(T n) { return range<T>(0, n); }
template<typename T> void take(vector<T>& vec, int n) { vec.resize(n); for (int i = 0; i < n; ++i) cin >> vec[i]; }
template<class... Args> void sout(const Args &...args) { ((cout << args << ' '), ...); }
template<class... Args> void soutn(const Args &...args) { ((cout << args << ' '), ...); cout << '\n'; }
template<typename T1, typename T2> struct In2 {
  T1 a; T2 b; friend std::istream& operator>>(std::istream& is, In2& obj) { T1 t1; T2 t2; is >> t1 >> t2; obj = {t1, t2}; return is; } };
template<typename T1, typename T2, typename T3> struct In3 {
  T1 a; T2 b; T3 c; friend std::istream& operator>>(std::istream& is, In3& obj) { T1 t1; T2 t2; T3 t3; is >> t1 >> t2 >> t3; obj = {t1, t2, t3}; return is; } };
template<typename T1, typename T2, typename T3, typename T4> struct In4 {
  T1 a; T2 b; T3 c; T4 d; friend std::istream& operator>>(std::istream& is, In4& obj) { T1 t1; T2 t2; T3 t3; T4 t4; is >> t1 >> t2 >> t3 >> t4; obj = {t1, t2, t3, t4}; return is; } };

#ifdef LOCAL
#include <debug.h>
#else
#define dump(...) ;
#endif

const ll mod = 924844033;
struct mint {
  ll x;
  mint(ll x_ = 0) : x((x_ % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint &a) { if ((x += a.x) >= mod) x -= mod; return *this; }
  mint &operator-=(const mint &a) { if ((x += mod - a.x) >= mod) x -= mod; return *this; }
  mint &operator*=(const mint &a) { (x *= a.x) %= mod; return *this; }
  mint operator+(const mint &a) const { mint res(*this); return res += a; }
  mint operator-(const mint &a) const { mint res(*this); return res -= a; }
  mint operator*(const mint &a) const { mint res(*this); return res *= a; }
  mint pow(ll t) const { if (!t) return 1; mint a = pow(t >> 1); a *= a; if (t & 1) a *= *this; return a; }
  mint inv() const { return pow(mod - 2); }
  mint &operator/=(const mint &a) { return (*this) *= a.inv(); }
  mint operator/(const mint &a) const { mint res(*this); return res /= a; }
  auto operator<=>(const mint&) const = default;
  friend ostream &operator<<(ostream &os, const mint &m) { os << m.x; return os; }
  friend istream &operator>>(istream &is, mint &m) { is >> m.x; return is; }
};

vector<mint> fact, invfact;
void prepare(int n) {
  fact.resize(n + 1);
  invfact.resize(n + 1);
  fact[0] = 1;
  for (int i : range(n)) fact[i + 1] = fact[i] * (i + 1);
  invfact[n] = fact[n].inv();
  for (int i = n; i >= 1; --i) invfact[i - 1] = invfact[i] * i;
}

mint combin(int n, int r) {
  if (r < 0 || r > n) return mint(0);
  return fact[n] * invfact[r] * invfact[n - r];
}

using Poly = vector<ll>;
Poly power(Poly a, ll b) {
  if (b == 0)
    return {1};
  if (b % 2)
    return atcoder::convolution<mod>(a, power(a, b - 1));
  else {
    Poly x = power(a, b / 2);
    return atcoder::convolution<mod>(x, x);
  }
}


template <typename T>
vector<vector<vector<vector<T>>>> make_vector4d(int x, int y, int z, int w, T init) {
  return vector<vector<vector<vector<T>>>>(x,
      vector<vector<vector<T>>>(y,
        vector<vector<T>>(z,
          vector<T>(w, init)
        )
      )
  );
}

namespace {

ll a, b, c;

void read() {
  cin >> a >> b >> c;
}

mint naive() {
  auto dp = make_vector4d(a + 1, b + 1, c + 1, 6, mint(0));
  dp[0][0][0][0] = 1;

  vector<int> toa{1, 0, 3, 2, 5, 4};
  vector<int> tob{5, 3, 4, 1, 2, 0};
  vector<int> toc{2, 4, 0, 5, 1, 3};

  for (int a0 : range(a + 1))
  for (int b0 : range(b + 1))
  for (int c0 : range(c + 1))
  for (int v : range(6)) {
    if (a0 + b0 + c0 == 0) continue;

    if (a0 > 0) dp[a0][b0][c0][v] += dp[a0 - 1][b0][c0][toa[v]];
    if (b0 > 0) dp[a0][b0][c0][v] += dp[a0][b0 - 1][c0][tob[v]];
    if (c0 > 0) dp[a0][b0][c0][v] += dp[a0][b0][c0 - 1][toc[v]];
  }

  dump("NAIVE", dp[a][b][c][0]);
  return dp[a][b][c][0];
}

void naive_better() {
  auto dp = make_vector4d(a + 1, b + 1, c + 1, 1, mint(0));
  dp[0][0][0][0] = mint(-1);

  for (int a0 : range(a + 1))
  for (int b0 : range(b + 1))
  for (int c0 : range(c + 1)) {
    if (a0 + b0 + c0 == 0) continue;

    if (a0 >= 2) dp[a0][b0][c0][0] += dp[a0 - 2][b0][c0][0];
    if (b0 >= 2) dp[a0][b0][c0][0] += dp[a0][b0 - 2][c0][0];
    if (c0 >= 2) dp[a0][b0][c0][0] += dp[a0][b0][c0 - 2][0];

    if (a0 >= 1 && b0 >= 1) dp[a0][b0][c0][0] -= dp[a0 - 1][b0 - 1][c0][0];
    if (b0 >= 1 && c0 >= 1) dp[a0][b0][c0][0] -= dp[a0][b0 - 1][c0 - 1][0];
    if (c0 >= 1 && a0 >= 1) dp[a0][b0][c0][0] -= dp[a0 - 1][b0][c0 - 1][0];
  }

  mint base = fact[a + b + c] * invfact[a] * invfact[b] * invfact[c];
  mint s = dp[a][b][c][0];
  mint t = (base - s * 2) / 3;
  dump("NAIVE BETTER S", s);
  dump("NAIVE BETTER ans", t);
}

void naive_better_rot() {
  auto dp = vector<vector<mint>>(a + 3, vector<mint>(b + 3));
  dp[0][0] = -1;

  for (int it : range((a + b + c) / 2)) {
    auto next = vector<vector<mint>>(a + 3, vector<mint>(b + 3));

    for (int a0 : range(a + 1))
    for (int b0 : range(b + 1)) {
      next[a0 + 0][b0 + 0] += dp[a0][b0];
      next[a0 + 1][b0 + 0] -= dp[a0][b0];
      next[a0 + 1][b0 + 1] -= dp[a0][b0];
      next[a0 + 0][b0 + 1] -= dp[a0][b0];
      next[a0 + 0][b0 + 2] += dp[a0][b0];
      next[a0 + 2][b0 + 0] += dp[a0][b0];
    }

    dp.swap(next);
  }

  dump("NAIVE BETTER ROT S=", dp[a][b]);
}

mint sign(int m) { return m % 2 ? -1 : 1; }

mint run() {
  if ((a + b + c) % 2) return 0;

  ll n = (a + b + c) / 2;

  prepare(2 * n + 10);

  Poly T{1, mod - 1, 1};
  Poly Tn = power(T, n);

  mint res;
  for (ll k : range(2 * n + 1)) {
    dump("====");
    dump(k);
    dump(Tn[k]);
    dump(combin(k, a) * sign(k - a));
    dump(combin(2 * n - k, b) * sign(2 * n - k - b));
    res += mint(Tn[k]) * combin(k, a) * sign(k - a) * combin(2 * n - k, b) * sign(2 * n - k - b);
  }
  res = -res;
  dump("FINAL S", res);

  mint base = fact[a + b + c] * invfact[a] * invfact[b] * invfact[c];
  res = (base - res * 2) / 3;
  dump("FINAL ans", res);

  return res;
}

void nop() {
  naive();
  naive_better();
  naive_better_rot();
}

}  // namespace

template <typename F>
void exec(F f) { if constexpr (std::is_same_v<decltype(f()), void>) f(); else cout << f() << endl; }

int main(int argc, char** argv) {
  cerr << fixed << setprecision(12);
  cout << fixed << setprecision(12);
  int testcase = 1;
  if (argc > 1) testcase = atoi(argv[1]);
  while (testcase--) {
    read();
  }
  exec(run);
}