結果
| 問題 | No.1321 塗るめた |
| ユーザー |
 polylogK
|
| 提出日時 | 2020-12-10 18:53:49 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 4,258 bytes |
| コンパイル時間 | 711 ms |
| コンパイル使用メモリ | 78,340 KB |
| 実行使用メモリ | 69,468 KB |
| 最終ジャッジ日時 | 2023-10-20 01:23:05 |
| 合計ジャッジ時間 | 5,166 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,348 KB |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
ソースコード
#line 1 "main.cpp"
#include <stdio.h>
#include <vector>
template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
#line 1 "/home/ecasdqina/cpcpp/libs/library_cpp/math/modint.hpp"
#include <iostream>
namespace cplib {
template <std::uint_fast64_t Modulus>
class modint {
using u32 = std::uint_fast32_t;
using u64 = std::uint_fast64_t;
using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
inline u64 apply(i64 x) { return (x < 0 ? x + Modulus : x); };
public:
u64 a;
static constexpr u64 mod = Modulus;
constexpr modint(const i64& x = 0) noexcept: a(apply(x % (i64)Modulus)) {}
constexpr modint operator+(const modint& rhs) const noexcept { return modint(*this) += rhs; }
constexpr modint operator-(const modint& rhs) const noexcept { return modint(*this) -= rhs; }
constexpr modint operator*(const modint& rhs) const noexcept { return modint(*this) *= rhs; }
constexpr modint operator/(const modint& rhs) const noexcept { return modint(*this) /= rhs; }
constexpr modint operator^(const u64& k) const noexcept { return modint(*this) ^= k; }
constexpr modint operator^(const modint& k) const noexcept { return modint(*this) ^= k.value(); }
constexpr modint operator-() const noexcept { return modint(Modulus - a); }
constexpr modint operator++() noexcept { return (*this) = modint(*this) + 1; }
constexpr modint operator--() noexcept { return (*this) = modint(*this) - 1; }
const bool operator==(const modint& rhs) const noexcept { return a == rhs.a; };
const bool operator!=(const modint& rhs) const noexcept { return a != rhs.a; };
const bool operator<=(const modint& rhs) const noexcept { return a <= rhs.a; };
const bool operator>=(const modint& rhs) const noexcept { return a >= rhs.a; };
const bool operator<(const modint& rhs) const noexcept { return a < rhs.a; };
const bool operator>(const modint& rhs) const noexcept { return a > rhs.a; };
constexpr modint& operator+=(const modint& rhs) noexcept {
a += rhs.a;
if (a >= Modulus) a -= Modulus;
return *this;
}
constexpr modint& operator-=(const modint& rhs) noexcept {
if (a < rhs.a) a += Modulus;
a -= rhs.a;
return *this;
}
constexpr modint& operator*=(const modint& rhs) noexcept {
a = a * rhs.a % Modulus;
return *this;
}
constexpr modint& operator/=(modint rhs) noexcept {
u64 exp = Modulus - 2;
while (exp) {
if (exp % 2) (*this) *= rhs;
rhs *= rhs;
exp /= 2;
}
return *this;
}
constexpr modint& operator^=(u64 k) noexcept {
auto b = modint(1);
while(k) {
if(k & 1) b = b * (*this);
(*this) *= (*this);
k >>= 1;
}
return (*this) = b;
}
constexpr modint& operator=(const modint& rhs) noexcept {
a = rhs.a;
return (*this);
}
const modint inverse() const {
return modint(1) / *this;
}
const modint power(i64 k) const {
if(k < 0) return modint(*this).inverse() ^ (-k);
return modint(*this) ^ k;
}
explicit operator bool() const { return a; }
explicit operator u64() const { return a; }
constexpr u64& value() noexcept { return a; }
constexpr const u64& value() const noexcept { return a; }
friend std::ostream& operator<<(std::ostream& os, const modint& p) {
return os << p.a;
}
friend std::istream& operator>>(std::istream& is, modint& p) {
u64 t;
is >> t;
p = modint(t);
return is;
}
};
}
#line 13 "main.cpp"
using mint = cplib::modint<998244353>;
int main() {
int n, m, K; scanf("%d%d%d", &n, &m, &K);
std::vector<mint> fact(n + 1, 1);
for(int i = 0; i < n; i++) fact[i + 1] = fact[i] * (i + 1);
auto comb = make_v<mint>(n + 1, n + 1);
for(int i = 0; i <= n; i++) for(int j = 0; j <= i; j++) comb[i][j] = fact[i] / fact[j] / fact[i - j];
auto dp = make_v<mint>(n + 1, K + 2); dp[0][0] = 1;
for(int i = 0; i < m; i++) {
auto nxt = make_v<mint>(n + 1, K + 2);
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= K; j++) {
for(int k = 0; i + k <= n; k++) {
nxt[i + k][j + !!k] += comb[n - i][k] * (mint(2).power(k) - 1) * dp[i][j];
nxt[i + k][j] += comb[n - i][k] * 1 * dp[i][j];
}
}
}
dp.swap(nxt);
}
printf("%lld\n", dp[n][K].value());
return 0;
}