結果

問題 No.2575 Almost Increasing Sequence
コンテスト
ユーザー noshi91
提出日時 2023-12-01 12:25:24
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 908 ms / 10,000 ms
コード長 4,965 bytes
コンパイル時間 4,358 ms
コンパイル使用メモリ 265,572 KB
実行使用メモリ 10,820 KB
スコア 600,000
最終ジャッジ日時 2023-12-02 23:39:33
合計ジャッジ時間 23,516 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

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

using mint = atcoder::modint998244353;

template <class T> void dft(std::vector<T> &a) {
  atcoder::internal::butterfly(a);
}

template <class T> void inv_dft(std::vector<T> &a) {
  atcoder::internal::butterfly_inv(a);
  T c = (1 - T::mod()) / int(a.size());
  for (auto &e : a)
    e *= c;
}

int next_pow2(int n) { return 1 << (32 - __builtin_clz(n)); }

using Expo = std::array<int, 3>;

Expo add(Expo ex, int i) {
  ex[i]++;
  return ex;
}

constexpr int N = 30000;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int K;
  std::cin >> K;

  const int limit = N + 1;
  std::vector<mint> fact(limit, 1), ifact(limit);
  for (int i = 1; i < limit; i++)
    fact[i] = fact[i - 1] * i * i;
  ifact.back() = 1 / fact.back();
  for (int i = limit; i-- > 1;)
    ifact[i - 1] = ifact[i] * i * i;

  std::map<Expo, mint> target;
  target[{0, 0, 0}] = 1;
  for (int i = 0; i < 3; i++) {
    for (int j = i + 1; j < 3; j++) {
      for (int k = 0; k < 2; k++) {
        decltype(target) next;
        for (const auto &[ex, co] : target) {
          next[add(ex, j)] += co;
          next[add(ex, i)] -= co;
        }
        target = next;
      }
    }
  }

  using poly = std::vector<mint>;
  using poly2d = std::array<poly, 5>;
  using result = std::array<poly2d, 2>;

  poly ans(N + 4, 0);

  auto f = [&](auto &f, const int l, const int r) -> result {
    result res;
    if (r - l == 1) {
      return res;
    }
    const int m = (l + r) / 2;
    const result resL = f(f, l, m), resR = f(f, m, r);

    {
      const int sz = next_pow2((m - l) + (r - m) * 2);
      poly L(m - l), bufL, bufR, sum(sz);
      for (int i = l; i < m; i++) {
        L[i - l] = ifact[i];
      }
      for (int i = 0; i < 5; i++) {
        bufL = L, bufL.resize(sz), dft(bufL);
        bufR = resR[0][i], bufR.resize(sz), dft(bufR);
        for (int j = 0; j < sz; j++)
          sum[j] += bufL[j] * bufR[j];
        for (int i = l; i < m; i++)
          L[i - l] *= i;
      }
      inv_dft(sum);
      const int lift = l + m * 2;
      for (int i = 0; i < sz && lift + i < ans.size(); i++)
        ans[lift + i] += sum[i];
    }
    {
      const int sz = next_pow2((m - l) * 2 + (r - m));
      poly R(r - m), bufL, bufR, sum(sz);
      for (int i = m; i < r; i++) {
        R[i - m] = ifact[i] * mint(i - 2).pow(K);
      }
      for (int i = 0; i < 5; i++) {
        bufL = resL[1][i], bufL.resize(sz), dft(bufL);
        bufR = R, bufR.resize(sz), dft(bufR);
        for (int j = 0; j < sz; j++)
          sum[j] += bufL[j] * bufR[j];
        for (int i = m; i < r; i++)
          R[i - m] *= i;
      }
      inv_dft(sum);
      const int lift = l * 2 + m;
      for (int i = 0; i < sz && lift + i < ans.size(); i++)
        ans[lift + i] += sum[i];
    }
    {
      const int sz = next_pow2(r - l);
      poly2d L, R;
      for (int i = 0; i < 5; i++) {
        L[i].resize(sz);
        for (int j = l; j < m; j++)
          L[i][j - l] = ifact[j] * mint(j).pow(i);
        dft(L[i]);
        R[i].resize(sz);
        for (int j = m; j < r; j++)
          R[i][j - m] = ifact[j] * mint(j).pow(i) * mint(j - 2).pow(K);
        dft(R[i]);
        res[0][i].resize(sz);
      }
      for (const auto &[ex, co] : target) {
        const auto &[a, b, c] = ex;
        for (int i = 0; i < sz; i++)
          res[0][a][i] += co * L[b][i] * R[c][i];
      }
      for (int i = 0; i < 5; i++) {
        inv_dft(res[0][i]);
        res[0][i].insert(res[0][i].begin(), m - l, mint(0));
        res[0][i].resize((r - l) * 2);
        for (int j = 0; j < resL[0][i].size(); j++)
          res[0][i][j] += resL[0][i][j];
        for (int j = 0; j < resR[0][i].size(); j++)
          res[0][i][(m - l) * 2 + j] += resR[0][i][j];
      }
    }
    {
      const int sz = next_pow2(r - l);
      poly2d L, R;
      for (int i = 0; i < 5; i++) {
        L[i].resize(sz);
        for (int j = l; j < m; j++)
          L[i][j - l] = ifact[j] * mint(j).pow(i);
        dft(L[i]);
        R[i].resize(sz);
        for (int j = m; j < r; j++)
          R[i][j - m] = ifact[j] * mint(j).pow(i);
        dft(R[i]);
        res[1][i].resize(sz);
      }
      for (const auto &[ex, co] : target) {
        const auto &[a, b, c] = ex;
        for (int i = 0; i < sz; i++)
          res[1][c][i] += co * L[a][i] * R[b][i];
      }
      for (int i = 0; i < 5; i++) {
        inv_dft(res[1][i]);
        res[1][i].insert(res[1][i].begin(), m - l, mint(0));
        res[1][i].resize((r - l) * 2);
        for (int j = 0; j < resL[1][i].size(); j++)
          res[1][i][j] += resL[1][i][j];
        for (int j = 0; j < resR[1][i].size(); j++)
          res[1][i][(m - l) * 2 + j] += resR[1][i][j];
      }
    }
    return res;
  };
  f(f, 1, N + 1);

  std::cout << N << "\n";
  for (int i = 1; i <= N; i++) {
    std::cout << (ans[i + 3] * fact[i]).val() << " \n"[i == N];
  }

  return 0;
}
0