結果

問題 No.2349 Power!! (Hard)
コンテスト
ユーザー ytqm3
提出日時 2023-06-10 21:33:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 938 ms / 7,000 ms
コード長 2,705 bytes
コンパイル時間 4,940 ms
コンパイル使用メモリ 263,440 KB
最終ジャッジ日時 2025-02-14 01:25:23
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;

template <class mint> vector<mint> MiddleProd(vector<mint> f, vector<mint> g) {
  int N = f.size(), M = g.size();
  assert(N >= M);
  reverse(g.begin(), g.end());
  vector<mint> h = atcoder::convolution(f, g);
  vector<mint> res(N - M + 1);
  for (int i = M - 1; i < N; ++i) {
    res[i - (M - 1)] = h[i];
  }
  return res;
}

template <class mint>
vector<mint> MultiEvalGeomSeq(vector<mint> f, mint r, int M) {
  if (f.size() == 0) {
    vector<mint> res(M);
    return res;
  }
  int N = f.size();
  auto calc = [&](mint q, int K) {
    // q^Tr(i) を計算
    vector<mint> res(K, 1);
    mint nw = 1;
    for (int i = 1; i < K; ++i) {
      nw *= q;
      res[i] = res[i - 1] * nw;
    }
    return res;
  };
  vector<mint> A = calc(r, N + M - 1), B = calc(mint(1) / r, max(N, M));
  for (int i = 0; i < N; ++i) {
    f[i] *= B[i];
  }
  auto g = MiddleProd(A, f);
  for (int i = 0; i < M; ++i) {
    g[i] *= B[i];
  }
  return g;
}

template <class mint> void AllInv(vector<mint> &f) {
  int n = f.size();
  vector<mint> res(n + 1, 1);
  for (int i = 0; i < n; ++i) {
    res[i + 1] = res[i] * f[i];
  }
  mint t = mint(1) / res[n];
  res.pop_back();
  for (int i = n - 1; i >= 0; --i) {
    res[i] *= t;
    t *= f[i];
  }
  f = move(res);
}

void solve() {
  constexpr i64 P = 998244353, D = (1 << 13) * 119, E = (P - 1) / D;
  using mint = atcoder::static_modint<P>;
  i64 A, N;
  cin >> A >> N;
  i64 L = N / D, R = N % D;
  mint nw, nw2, cff;
  auto h = [&](int n) {
    i64 m = n / E;
    vector<mint> g(m);
    mint ee = mint(A).pow(E * E);
    nw = 1, cff = 1;
    for (i64 i = 0; i < m; ++i) {
      g[i] = nw;
      nw *= ee * cff;
      cff *= ee * ee;
    }
    auto W = MultiEvalGeomSeq(g, mint(A).pow(2 * E), E);
    vector<mint> res(E);
    nw = 1, cff = 1;
    for (i64 i = 0; i < E; ++i) {
      res[i] += nw * W[i];
      nw *= A * cff;
      cff *= A * A;
    }
    nw = mint(A).pow(m * m * E * E), cff = mint(A).pow(2 * m * E);
    for (i64 i = m * E; i < n; ++i) {
      res[i % E] += nw;
      nw *= A * cff;
      cff *= A * A;
    }
    return res;
  };
  vector<mint> X = h(D), Y = h(R);
  mint ans = 0, d2 = mint(A).pow(2 * D), ld2 = mint(A).pow(2 * L * D);
  nw = 1;
  vector<mint> Inv(E);
  for (i64 t = 0; t < E; ++t) {
    Inv[t] = -nw + 1;
    if (Inv[t] == 0) {
      Inv[t] = 1;
    }
    nw *= d2;
  }
  AllInv(Inv);
  nw = 1, nw2 = 1;
  for (i64 t = 0; t < E; ++t) {
    ans += (nw2 == mint(1) ? L : (-nw + 1) * Inv[t]) * X[t] + nw * Y[t];
    nw *= ld2;
    nw2 *= d2;
  }
  cout << ans.val() << endl;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    solve();
  }
}
0