結果
問題 | No.1923 Divisor Array |
ユーザー | ebi_fly |
提出日時 | 2022-05-01 23:16:21 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 56 ms / 2,000 ms |
コード長 | 4,292 bytes |
コンパイル時間 | 753 ms |
コンパイル使用メモリ | 80,220 KB |
実行使用メモリ | 34,716 KB |
最終ジャッジ日時 | 2023-09-14 06:33:24 |
合計ジャッジ時間 | 3,393 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 56 ms
34,716 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 39 ms
24,444 KB |
testcase_05 | AC | 21 ms
13,788 KB |
testcase_06 | AC | 43 ms
30,208 KB |
testcase_07 | AC | 21 ms
14,440 KB |
testcase_08 | AC | 23 ms
15,732 KB |
testcase_09 | AC | 50 ms
32,384 KB |
testcase_10 | AC | 17 ms
11,800 KB |
testcase_11 | AC | 19 ms
13,572 KB |
testcase_12 | AC | 26 ms
17,040 KB |
testcase_13 | AC | 16 ms
11,192 KB |
testcase_14 | AC | 1 ms
4,380 KB |
testcase_15 | AC | 1 ms
4,380 KB |
testcase_16 | AC | 1 ms
4,380 KB |
testcase_17 | AC | 1 ms
4,376 KB |
testcase_18 | AC | 2 ms
4,380 KB |
testcase_19 | AC | 1 ms
4,376 KB |
testcase_20 | AC | 2 ms
4,376 KB |
testcase_21 | AC | 1 ms
4,376 KB |
testcase_22 | AC | 2 ms
4,376 KB |
testcase_23 | AC | 2 ms
4,380 KB |
testcase_24 | AC | 26 ms
16,956 KB |
testcase_25 | AC | 34 ms
22,176 KB |
testcase_26 | AC | 43 ms
26,420 KB |
testcase_27 | AC | 38 ms
23,620 KB |
testcase_28 | AC | 21 ms
14,420 KB |
testcase_29 | AC | 16 ms
10,936 KB |
testcase_30 | AC | 26 ms
16,768 KB |
testcase_31 | AC | 41 ms
25,004 KB |
testcase_32 | AC | 42 ms
25,676 KB |
testcase_33 | AC | 33 ms
21,192 KB |
testcase_34 | AC | 1 ms
4,380 KB |
testcase_35 | AC | 1 ms
4,376 KB |
testcase_36 | AC | 2 ms
4,376 KB |
testcase_37 | AC | 1 ms
4,380 KB |
testcase_38 | AC | 2 ms
4,376 KB |
testcase_39 | AC | 10 ms
9,112 KB |
testcase_40 | AC | 35 ms
27,872 KB |
testcase_41 | AC | 7 ms
7,348 KB |
testcase_42 | AC | 39 ms
31,468 KB |
testcase_43 | AC | 13 ms
11,340 KB |
testcase_44 | AC | 1 ms
4,376 KB |
testcase_45 | AC | 1 ms
4,380 KB |
testcase_46 | AC | 1 ms
4,376 KB |
testcase_47 | AC | 1 ms
4,376 KB |
testcase_48 | AC | 2 ms
4,380 KB |
testcase_49 | AC | 2 ms
4,380 KB |
testcase_50 | AC | 2 ms
4,380 KB |
testcase_51 | AC | 1 ms
4,376 KB |
testcase_52 | AC | 1 ms
4,380 KB |
testcase_53 | AC | 2 ms
4,376 KB |
ソースコード
#include <cassert> #include <cstdint> #include <iostream> #include <vector> /* 計算量: O(M^2 + M\log{M}\log{K}) */ /* macro */ #define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++) #define rrep(i, a, n) for (int i = ((int)(n - 1)); i >= (int)(a); i--) /* macro end */ namespace ebi { template <std::uint_fast64_t Modulus> class modint { using u64 = std::uint_fast64_t; public: u64 a; constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {} constexpr u64 &value() noexcept { return a; } constexpr u64 &val() noexcept { return a; } constexpr const u64 &value() const noexcept { return a; } 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 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-() const { return modint() - *this; } bool operator==(const u64 rhs) { return a == rhs; } bool operator!=(const u64 rhs) { return a != rhs; } constexpr modint &operator++() { a++; if (a == mod()) a = 0; return *this; } constexpr modint &operator--() { if (a == 0) a = mod(); a--; return *this; } modint pow(u64 n) const noexcept { modint res = 1; modint x = a; while (n > 0) { if (n & 1) res *= x; x *= x; n >>= 1; } return res; } modint inv() const { return pow(Modulus - 2); } static u64 mod() { return Modulus; } }; using modint998244353 = modint<998244353>; using modint1000000007 = modint<1000000007>; template <std::uint_fast64_t Modulus> std::ostream &operator<<(std::ostream &os, modint<Modulus> a) { return os << a.val(); } } // namespace ebi using mint = ebi::modint998244353; int main() { int n, m, k; std::cin >> n >> m >> k; std::vector dp(m + 1, std::vector<mint>(m, 0)); dp[0][0] = 1; rep(i, 0, m) { rep(j, 0, m) { if (j + 1 < m) dp[i + 1][j + 1] += dp[i][j] + dp[i + 1][j]; if (2 * j + 2 < m) dp[i + 1][2 * j + 2] -= dp[i][j]; } } std::vector<mint> ret(m + 1, 0); std::vector<mint> fact(m + 1, 1), inv(m + 1, 1); rep(i, 0, m) { fact[i + 1] = fact[i] * mint(n - i); inv[i + 1] = inv[i] * mint(i + 1); } inv[m] = inv[m].inv(); rrep(i, 0, m) { inv[i] = inv[i + 1] * mint(i + 1); } auto comb = [&](int r) -> mint { assert(0 <= r && r <= m); return fact[r] * inv[r]; }; rep(i, 0, std::min(n, m) + 1) { rep(j, 0, m) { ret[j + 1] += dp[i][j] * comb(i); } } std::vector<mint> now(m + 1, 0); now[1] = 1; auto mul = [&m](const std::vector<mint> &lhs, const std::vector<mint> &rhs) -> std::vector<mint> { std::vector<mint> res(m + 1, 0); for (int i = 1; i < m + 1; i++) { for (int j = 1; i * j < m + 1; j++) { res[i * j] += lhs[i] * rhs[j]; } } return res; }; while (k > 0) { if (k & 1) { now = mul(now, ret); } ret = mul(ret, ret); k >>= 1; } mint ans = 0; for (int i = 0; i < m + 1; i++) { ans += now[i]; } std::cout << ans.val() << '\n'; }