結果

問題 No.1492 01文字列と転倒
ユーザー CyanmondCyanmond
提出日時 2021-04-30 22:04:04
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 486 ms / 4,000 ms
コード長 3,858 bytes
コンパイル時間 2,113 ms
コンパイル使用メモリ 204,820 KB
実行使用メモリ 406,036 KB
最終ジャッジ日時 2023-09-26 06:07:51
合計ジャッジ時間 7,185 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 482 ms
406,036 KB
testcase_03 AC 434 ms
375,048 KB
testcase_04 AC 399 ms
345,604 KB
testcase_05 AC 337 ms
292,488 KB
testcase_06 AC 350 ms
305,092 KB
testcase_07 AC 393 ms
331,656 KB
testcase_08 AC 486 ms
405,800 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 364 ms
305,000 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 8 ms
8,900 KB
testcase_17 AC 349 ms
292,384 KB
testcase_18 AC 8 ms
9,520 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 6 ms
7,192 KB
testcase_21 AC 285 ms
245,672 KB
testcase_22 AC 8 ms
8,892 KB
testcase_23 AC 4 ms
5,524 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#pragma region cscpptemp
// require at least C++17 to compile
using llint = long long int;
template <class T>
using Heap = std::priority_queue<T>;
template <class T>
using RevHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

// ex. for (const int i : range(a, b)) ... loop [a, b)
template <class T, class = std::enable_if_t<std::is_signed_v<T>>>
class range {
  struct range_iterator {
    T itr;
    constexpr range_iterator(const int pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { ++itr; }
    constexpr bool operator!=(const range_iterator& other) const noexcept {
      return itr != other.itr;
    }
    constexpr T operator*() const noexcept { return itr; }
  };

 public:
  constexpr range(const T first_, const T last_) noexcept
      : first(first_), last(last_) {}
  constexpr range_iterator begin() const noexcept { return first; }
  constexpr range_iterator end() const noexcept { return last; }

 private:
  const range_iterator first, last;
};

// ex. for (const int i : range(a, b)) ... revloop [a, b]
template <class T, class = std::enable_if_t<std::is_signed_v<T>>>
class revrange {
  struct revrange_iterator {
    T itr;
    constexpr revrange_iterator(const int pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { --itr; }
    constexpr bool operator!=(const revrange_iterator& other) const noexcept {
      return itr != other.itr;
    }
    constexpr T operator*() const noexcept { return itr; }
  };

 public:
  constexpr revrange(const T first_, const T last_) noexcept
      : first(first_), last(last_ - 1) {}
  constexpr revrange_iterator begin() const noexcept { return first; }
  constexpr revrange_iterator end() const noexcept { return last; }

 private:
  const revrange_iterator first, last;
};

// ex. rec_lambda([](auto&& f, int n) -> int {return n < 1 ? 1 : f(--n); })
template <class F>
class rec_lambda {
 public:
  constexpr rec_lambda(F&& f_) : f(std::forward<F>(f_)) {}
  template <class... Args>
  constexpr auto operator()(Args&&... args) const {
    return f(*this, std::forward<Args>(args)...);
  }

 private:
  F f;
};

// ex. const int N = read()
struct read {
  template <class T>
  operator T() {
    T ret;
    std::cin >> ret;
    return ret;
  }
};

// ex. chmax(a, b) ... a = max(a, b)
template <class T>
constexpr void chmax(T& a, const T b) noexcept {
  if (a < b) a = b;
}
template <class T>
constexpr void chmin(T& a, const T b) noexcept {
  if (a > b) a = b;
}

// ex. ceildiv(a, b) ... ceil(a / b)
template <class T, class = std::enable_if_t<std::is_integral_v<T>>>
constexpr T ceildiv(const T dividend, const T divisor) {
  return (dividend + divisor - 1) / divisor;
}

// ex. mk_vec(a, b, c, v) ... 3D vector size: [a][b][c] init value: v
template <class T>
auto mk_vec(const int n, const T value) {
  return std::vector(n, value);
}
template <class... Args>
auto mk_vec(const int n, Args... args) {
  return std::vector(n, mk_vec(args...));
}
#pragma endregion

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  const int N = read();
  const int M = read();  // M is prime
  // 0sum <= 1sum (all i)
  std::vector DP(N + 1, std::vector(N + 1, std::vector(N * N + 1, 0)));
  /* (0, 1) = (a, b)
   * invnum = k
   * DP[a + 1][b]
   */
  DP[0][0][0] = 1;
  for (const int a : range(0, N + 1))
    for (const int b : range(0, a + 1))
      for (const int k : range(0, N * N + 1)) {
        if (a != N and k + b <= N * N) {
          DP[a + 1][b][k + b] += DP[a][b][k];
          if (DP[a + 1][b][k + b] >= M) DP[a + 1][b][k + b] -= M;
        }
        if (a > b) {
          DP[a][b + 1][k] += DP[a][b][k];
          if (DP[a][b + 1][k] >= M) DP[a][b + 1][k] -= M;
        }
      }
  for (const int i : range(0, N * N + 1)) std::cout << DP[N][N][i] << '\n';
  // .............
  return 0;
}
0