#1175623 (C++23(gcc16)) No.3399 One Two Three Two Three

• 問題: No.3399 One Two Three Two Three
• ユーザー: Phartial
• 提出日時: 2026-08-07 16:24:13
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 731 ms / 4,000 ms
• コード長: 2,683 bytes
• コンパイル時間: 5,160 ms
• コンパイル使用メモリ: 270,176 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-08-07 16:24:28
• 合計ジャッジ時間: 14,163 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 5
other	AC * 40

ソースコード

#include <algorithm>
#include <atcoder/convolution>
#include <iostream>
#include <ranges>
#include <vector>

using namespace std;
using ll = long long;
using mint = atcoder::modint998244353;
using atcoder::convolution;
namespace rg = ranges;
namespace vw = rg::views;

using poly = vector<mint>;
poly& operator+=(poly& f, const poly& g) {
  if (f.size() < g.size()) {
    f.resize(g.size());
  }
  for (size_t i = 0; i < g.size(); ++i) {
    f[i] += g[i];
  }
  return f;
}
poly operator+(poly f, const poly& g) { return f += g; }
poly& operator*=(poly& f, const poly& g) { return f = convolution(f, g); }
poly operator*(const poly& f, const poly& g) { return convolution(f, g); }

int main() {
  cin.tie(0)->sync_with_stdio(0);
  ll n;
  cin >> n;
  auto F2 = [](const poly& f) {
    auto g = f;
    rg::for_each(g | vw::drop(1) | vw::stride(2), [](mint& v) { v = -v; });
    return g;
  };
  auto F3 = [](const poly& f) {
    auto m = f.size();
    vector<mint> x(m), y(m), z(m);
    for (size_t i = 0; i < m; ++i) {
      if (i % 3 == 0) {
        x[i] = y[i] = f[i];
      } else if (i % 3 == 1) {
        x[i] = -f[i], z[i] = f[i];
      } else if (i % 3 == 2) {
        y[i] = z[i] = -f[i];
      }
    }
    return x * y + z * z;
  };
  const poly b{1, -1, -1, -1};
  vector<poly> h2(__lg(n) + 1);
  h2[0] = {1};
  for (int i = 1; i <= __lg(n); ++i) {
    const auto _h = h2[i - 1] * b;
    h2[i] = poly(from_range, (_h * F2(_h)) | vw::stride(2));
  }
  mint ans = 0;
  vector<pair<poly, poly>> f(__lg(n) + 2), g(__lg(n) + 2);
  f[0] = {poly{1}, poly{1}};
  for (poly h3{1};; n /= 3) {
    fill(g.begin(), g.end(), pair{poly{}, poly{}});
    poly r{0};
    ll _n = n;
    for (int i = 0;; _n >>= 1, ++i) {
      auto [p, q] = f[i];
      if (_n == 0) {
        ans += r[0];
        break;
      }
      q *= b, r *= b;
      {
        auto _p = p;
        _p.insert(_p.begin(), 0);
        r += _p;
      }
      {
        auto t = F2(q);
        poly _r(from_range, (r * t) | vw::drop(_n & 1) | vw::stride(2));
        poly _p(from_range, (p * t) | vw::drop(_n & 1) | vw::stride(2));
        poly _q(from_range, (q * t) | vw::stride(2));
        r = _r * h3, _p *= h3, _q *= h3;
        f[i + 1].first += _p, f[i + 1].second = _q;
      }
      {
        auto t = F3(q);
        poly _p(from_range, (p * t) | vw::drop(_n % 3) | vw::stride(3));
        poly _q(from_range, (q * t) | vw::stride(3));
        _p *= h2[i], _q *= h2[i];
        g[i].first += _p, g[i].second = _q;
      }
    }
    swap(f, g);
    if (n == 0) {
      break;
    }
    const poly _h = h3 * b;
    h3 = poly(from_range, (_h * F3(_h)) | vw::stride(3));
  }
  cout << ans.val() << '\n';
  return 0;
}