結果
問題 |
No.3213 depth max K
|
ユーザー |
![]() |
提出日時 | 2025-07-25 22:24:21 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 626 ms / 2,000 ms |
コード長 | 3,723 bytes |
コンパイル時間 | 5,419 ms |
コンパイル使用メモリ | 215,808 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-07-25 22:24:38 |
合計ジャッジ時間 | 13,995 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <uint32_t mod_, bool fast = false> struct MontgomeryModInt { private: using mint = MontgomeryModInt; using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 get_r() { u32 ret = mod_; for (i32 i = 0; i < 4; i++) ret *= 2 - mod_ * ret; return ret; } static constexpr u32 r = get_r(); static constexpr u32 n2 = -u64(mod_) % mod_; static_assert(r * mod_ == 1, "invalid, r * mod != 1"); static_assert(mod_ < (1 << 30), "invalid, mod >= 2 ^ 30"); static_assert((mod_ & 1) == 1, "invalid, mod % 2 == 0"); u32 x; public: MontgomeryModInt() : x{} {} MontgomeryModInt(const i64 &a): x(reduce(u64(fast ? a : (a % mod() + mod())) * n2)) {} static constexpr u32 reduce(const u64 &b) { return u32(b >> 32) + mod() - u32((u64(u32(b) * r) * mod()) >> 32); } mint &operator+=(const mint &p) { if (i32(x += p.x - 2 * mod()) < 0) x += 2 * mod(); return *this; } mint &operator-=(const mint &p) { if (i32(x -= p.x) < 0) x += 2 * mod(); return *this; } mint &operator*=(const mint &p) { x = reduce(u64(x) * p.x); return *this; } mint &operator/=(const mint &p) { *this *= p.inv(); return *this; } mint operator-() const { return mint() - *this; } mint operator+(const mint &p) const { return mint(*this) += p; } mint operator-(const mint &p) const { return mint(*this) -= p; } mint operator*(const mint &p) const { return mint(*this) *= p; } mint operator/(const mint &p) const { return mint(*this) /= p; } bool operator==(const mint &p) const { return (x >= mod() ? x - mod() : x) == (p.x >= mod() ? p.x - mod() : p.x); } bool operator!=(const mint &p) const { return (x >= mod() ? x - mod() : x) != (p.x >= mod() ? p.x - mod() : p.x); } u32 val() const { u32 ret = reduce(x); return ret >= mod() ? ret - mod() : ret; } mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } mint inv() const { return pow(mod() - 2); } friend ostream &operator<<(ostream &os, const mint &p) { return os << p.val(); } friend istream &operator>>(istream &is, mint &a) { i64 t; is >> t; a = mint(t); return is; } static constexpr u32 mod() { return mod_; } }; template <uint32_t mod> using modint = MontgomeryModInt<mod>; using mint = modint<998244353>; mint f(int N, int K){ vector<mint> dp1(N + 1, 0), dp2(N + 1, 0); vector<mint> dp3(N + 1, 0), dp4(N + 1, 0); dp1[0] = 1; for(int i = 0; i < 2 * N; ++i){ dp3.clear(), dp4.clear(); dp3.assign(N + 1, 0); dp4.assign(N + 1, 0); for(int j = 0; j < K; ++j){ if(j != 0) dp3[j - 1] += dp1[j]; dp3[j + 1] += dp1[j]; } dp2[K] += dp1[K]; for(int j = 0; j <= N; ++j){ if(j != 0) dp4[j - 1] += dp2[j]; if(j != N) dp4[j + 1] += dp2[j]; } swap(dp1, dp3); swap(dp2, dp4); } return dp2[0]; } void solve(){ int N; cin >> N; int K; cin >> K; if(K == N){ cout << 1 << "\n"; return; } cout << f(N, K) - f(N, K + 1) << "\n"; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout << setprecision(10) << fixed; int T; T = 1; //cin >> T; for(;T--;) solve(); }