結果

問題 No.2575 Almost Increasing Sequence
ユーザー noshi91noshi91
提出日時 2023-11-07 05:24:16
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,020 bytes
コンパイル時間 4,066 ms
コンパイル使用メモリ 271,940 KB
実行使用メモリ 33,920 KB
スコア 0
最終ジャッジ日時 2023-12-02 23:38:58
合計ジャッジ時間 72,513 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
権限があれば一括ダウンロードができます

ソースコード

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;
}

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

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

Expo sum(Expo ex, const Expo &ey) {
  for (int i = 0; i < 4; i++)
    ex[i] += ey[i];
  return ex;
}

constexpr int N = 1000;

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

  int K;
  std::cin >> K;

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

  std::map<Expo, mint> target;
  target[{0, 0, 0, 0}] = 1;
  for (int i = 0; i < 4; i++) {
    for (int j = i + 1; j < 4; 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::map<Expo, poly>;
  using result = std::array<std::array<poly2d, 5>, 5>;

  auto f = [&](auto &f, int l, int r) -> result {
    result res;
    if (r - l == 1) {
      for (int i = 0; i < 5; i++)
        res[i][i][{0, 0, 0, 0}].push_back(1);
      for (int i = 0; i < 4; i++) {
        Expo ex = {0, 0, 0, 0};
        mint co = ifact[l] * ifact[l];
        if (i == 3)
          co *= mint(l - 3).pow(K);
        for (int j = 0; j <= 12; j++) {
          res[i][i + 1][ex].push_back(co);
          ex[i]++;
          co *= l;
        }
      }
      return res;
    }
    int m = l + (1 << (31 - __builtin_clz(r - l - 1)));
    auto resL = f(f, l, m);
    auto resR = f(f, m, r);
    int w = 4 << (32 - __builtin_clz(r - l - 1));
    std::array<poly, 5> lift;
    for (int i = 0; i < 5; i++) {
      lift[i].resize(w);
      lift[i][i * (m - l)] = 1;
      dft(lift[i]);
    }
    for (auto &r : resL)
      for (auto &e : r)
        for (auto &[ex, p] : e)
          p.resize(w), dft(p);
    for (auto &r : resR)
      for (auto &e : r)
        for (auto &[ex, p] : e)
          p.resize(w), dft(p);
    for (int hl = 0; hl < 5; hl++) {
      for (int hm = hl; hm < 5; hm++) {
        for (int hr = hm; hr < 5; hr++) {
          auto &lft = lift[hr - hm];
          if (hr - hl == 4 && (hm - hl == 1 || hr - hm == 1)) {
            auto &p = res[hl][hr][{0, 0, 0, 0}];
            p.resize(w);
            for (auto &[ex, pl] : resL[hl][hm]) {
              if (resR[hm][hr].count(ex)) {
                auto &pr = resR[hm][hr][ex];
                for (int i = 0; i < w; i++)
                  p[i] += lft[i] * pl[i] * pr[i];
              }
            }
          } else if (hr - hl == 4 && hm == hl + 2) {
            auto &p = res[hl][hr][{0, 0, 0, 0}];
            p.resize(w);
            for (auto &[exl, pl] : resL[hl][hm]) {
              for (auto &[exr, pr] : resR[hm][hr]) {
                mint c = target[sum(exl, exr)];
                if (c == mint(0))
                  continue;
                for (int i = 0; i < w; i++)
                  p[i] += c * lft[i] * pl[i] * pr[i];
              }
            }
          } else if (hr - hl == 3 && hl != hm && hm != hr) {
            for (auto &[exl, pl] : resL[hl][hm]) {
              for (auto &[exr, pr] : resR[hm][hr]) {
                Expo s = sum(exl, exr);
                int ref = 12 - (s[0] + s[1] + s[2] + s[3]);
                if (ref < 0)
                  continue;
                Expo t = {0, 0, 0, 0};
                (hl ? t[3] : t[0]) = ref;
                mint c = target[sum(s, t)];
                if (c == mint(0))
                  continue;
                auto &p = res[hl][hr][t];
                p.resize(w);
                for (int i = 0; i < w; i++)
                  p[i] += c * lft[i] * pl[i] * pr[i];
              }
            }
          } else {
            for (const auto &[exl, pl] : resL[hl][hm]) {
              for (const auto &[exr, pr] : resR[hm][hr]) {
                auto &p = res[hl][hr][sum(exl, exr)];
                p.resize(w);
                for (int i = 0; i < w; i++)
                  p[i] += lft[i] * pl[i] * pr[i];
              }
            }
          }
        }
      }
    }
    for (int hl = 0; hl < 5; hl++) {
      for (int hr = 0; hr < 5; hr++) {
        for (auto &[ex, p] : res[hl][hr]) {
          inv_dft(p);
        }
      }
    }
    return res;
  };

  auto ans = f(f, 1, N + 1)[0][4][{0, 0, 0, 0}];

  const int out = std::min(N, 1000);
  std::cout << out << "\n";
  for (int i = 1; i <= out; i++) {
    std::cout << (ans[i + 2] * fact[i] * fact[i]).val() << " \n"[i == out];
  }

  return 0;
}
0