結果

問題 No.3399 One Two Three Two Three
コンテスト
ユーザー noshi91
提出日時 2025-03-21 21:12:07
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,833 ms / 4,000 ms
コード長 2,342 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,809 ms
コンパイル使用メモリ 259,504 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-05 23:33:24
合計ジャッジ時間 29,744 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

#include <atcoder/convolution>
#include <atcoder/modint>

using mint = atcoder::modint998244353;
using poly = std::vector<mint>;

poly graeffe2(poly p) {
  assert(p.size() == 4 && p[0] == 1);
  return {{1, -p[1], p[2], -p[3]}};
}

poly graeffe3(poly p) {
  assert(p.size() == 4 && p[0] == 1);
  return {{1, -p[1], p[1] * p[1] - p[2], -p[1] * p[2] + 2 * p[3],
           -p[1] * p[3] + p[2] * p[2], -p[2] * p[3], p[3] * p[3]}};
}

void addassign(poly &p, poly q) {
  if (p.size() < q.size())
    std::swap(p, q);
  for (int i = 0; i < q.size(); i++)
    p[i] += q[i];
}

poly prod(poly p, poly q) { return atcoder::convolution(p, q); }

poly section(poly p, int d, int a) {
  poly q;
  while (a < p.size()) {
    q.push_back(p[a]);
    a += d;
  }
  return q;
}

int main() {
  long long n;
  std::cin >> n;

  auto gp = std::vector(61, std::vector(61, poly{}));
  gp[0][0] = {1, -1, -1, -1};
  for (int i = 1; i < 61; i++) {
    gp[i][0] = section(prod(gp[i - 1][0], graeffe2(gp[i - 1][0])), 2, 0);
  }
  for (int i = 0; i < 61; i++) {
    for (int j = 1; j < 61; j++) {
      gp[i][j] = section(prod(gp[i][j - 1], graeffe3(gp[i][j - 1])), 3, 0);
    }
  }

  struct state {
    poly p, q;
  };
  // [x^n](p+qf)/d

  std::map<long long, state> st;
  st[n] = state{{{}}, {{1}}};
  mint ans = 0;
  poly c2{{1}}, c2p{{1}}, c3{{1}}, c3p{{1}};
  for (int r = 0; r < 60; r++) {
    std::map<long long, state> nx;
    const auto add = [&](long long n, poly p, poly q) {
      if (n == 0) {
        ans += p[0];
      } else {
        addassign(nx[n].p, p);
        addassign(nx[n].q, q);
      }
    };

    for (int i = 0; i <= r; i++) {
      c2 = prod(c2, graeffe2(gp[i][r - i]));
      c3 = prod(c3, graeffe3(gp[i][r - i]));
    }
    c2p = prod(c2p, gp[0][r + 1]);
    c3p = prod(c3p, gp[r + 1][0]);

    for (const auto &[n, s] : st) {
      auto [p, q] = s;
      p = prod(p, {{1, -1, -1, -1}});
      addassign(p, prod({{0, 1}}, q));
      auto qq = q;
      {
        p = prod(section(prod(p, c2), 2, n % 2), c2p);
        q = prod(section(prod(q, c2), 2, n % 2), c2p);
        add(n / 2, p, q);
      }
      {
        qq = prod(section(prod(qq, c3), 3, n % 3), c3p);
        add(n / 3, {{}}, qq);
      }
    }

    st = std::move(nx);
  }
  assert(st.empty());

  std::cout << ans.val() << "\n";

  return 0;
}
0