結果

問題 No.2575 Almost Increasing Sequence
ユーザー noshi91noshi91
提出日時 2023-12-01 12:37:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 634 ms / 10,000 ms
コード長 4,452 bytes
コンパイル時間 4,140 ms
コンパイル使用メモリ 261,848 KB
実行使用メモリ 15,064 KB
スコア 600,000
最終ジャッジ日時 2023-12-02 23:39:17
合計ジャッジ時間 17,717 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 597 ms
15,064 KB
testcase_01 AC 595 ms
15,064 KB
testcase_02 AC 592 ms
15,064 KB
testcase_03 AC 599 ms
15,064 KB
testcase_04 AC 612 ms
15,064 KB
testcase_05 AC 614 ms
15,064 KB
testcase_06 AC 590 ms
15,064 KB
testcase_07 AC 606 ms
15,064 KB
testcase_08 AC 599 ms
15,064 KB
testcase_09 AC 584 ms
15,064 KB
testcase_10 AC 589 ms
15,064 KB
testcase_11 AC 588 ms
15,064 KB
testcase_12 AC 634 ms
15,064 KB
testcase_13 AC 595 ms
15,064 KB
testcase_14 AC 590 ms
15,064 KB
testcase_15 AC 600 ms
15,064 KB
testcase_16 AC 596 ms
15,064 KB
testcase_17 AC 593 ms
15,064 KB
testcase_18 AC 595 ms
15,064 KB
testcase_19 AC 593 ms
15,064 KB
権限があれば一括ダウンロードができます

ソースコード

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 pows(N + 1, 1);
  for (int i = 0; i <= N; i++)
    pows[i] = mint(i).pow(K);

  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;
    result resL = f(f, l, m), resR = f(f, m, r);

    const int osz = next_pow2((m - l) + (r - m) * 2);
    poly2d L0, R0, R1;
    for (int i = 0; i < 5; i++) {
      L0[i].resize(osz);
      for (int j = l; j < m; j++)
        L0[i][j - l] = ifact[j] * mint(j).pow(i);
      dft(L0[i]);
      R0[i].resize(osz);
      for (int j = m; j < r; j++)
        R0[i][j - m] = ifact[j] * mint(j).pow(i);
      dft(R0[i]);
      R1[i].resize(osz);
      for (int j = m; j < r; j++)
        R1[i][j - m] = ifact[j] * mint(j).pow(i) * pows[j - 2];
      dft(R1[i]);
    }

    {
      const int sz = next_pow2(r - l);
      for (int i = 0; i < 5; 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 * L0[b][i] * R1[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);
      for (int i = 0; i < 5; 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 * L0[a][i] * R0[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];
      }
    }

    {
      poly sum(osz);
      for (int i = 0; i < 5; i++) {
        resR[0][i].resize(osz), dft(resR[0][i]);
        for (int j = 0; j < osz; j++)
          sum[j] += L0[i][j] * resR[0][i][j];
      }
      inv_dft(sum);
      const int lift = l + m * 2;
      for (int i = 0; i < osz && lift + i < ans.size(); i++)
        ans[lift + i] += sum[i];
    }
    {
      poly sum(osz);
      for (int i = 0; i < 5; i++) {
        resL[1][i].resize(osz), dft(resL[1][i]);
        for (int j = 0; j < osz; j++)
          sum[j] += resL[1][i][j] * R1[i][j];
      }
      inv_dft(sum);
      const int lift = l * 2 + m;
      for (int i = 0; i < osz && lift + i < ans.size(); i++)
        ans[lift + i] += sum[i];
    }
    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