結果
問題 | No.3096 Snake Path |
ユーザー |
|
提出日時 | 2025-03-09 00:27:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 242 ms / 2,000 ms |
コード長 | 3,588 bytes |
コンパイル時間 | 3,812 ms |
コンパイル使用メモリ | 282,624 KB |
実行使用メモリ | 72,064 KB |
最終ジャッジ日時 | 2025-03-09 11:23:02 |
合計ジャッジ時間 | 7,697 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<int m> struct StaticModint { using mint = StaticModint; int _v; constexpr StaticModint() : _v(0) {} template<class T> constexpr StaticModint(T v) : _v((v % m + m) % m) {} constexpr int val() const { return _v; } constexpr mint& operator ++ () { return *this += 1; } constexpr mint& operator -- () { return *this -= 1; } constexpr mint operator ++ (int) { mint res = *this; ++*this; return res; } constexpr mint operator -- (int) { mint res = *this; --*this; return res; } constexpr mint& operator += (const mint& r) { if(_v >= m - r._v) _v -= m; _v += r._v; return *this; } constexpr mint& operator -= (const mint& r) { if(_v < r._v) _v += m; _v -= r._v; return *this; } constexpr mint& operator *= (const mint& r) { unsigned long long z = _v; z *= r._v; _v = (unsigned int)(z % m); return *this; } constexpr mint& operator /= (const mint& r) { return *this *= r.inv(); } constexpr mint pow(long long n) const { mint x = *this, r = 1; while(n) { if(n & 1) r *= x; x *= x; n >>= 1; } return r; } constexpr mint inv() const { return pow(m - 2); } constexpr mint operator + () const { return *this; } constexpr mint operator - () const { return mint() - *this; } constexpr mint operator + (const mint& r) const { return mint(*this) += r; } constexpr mint operator - (const mint& r) const { return mint(*this) -= r; } constexpr mint operator * (const mint& r) const { return mint(*this) *= r; } constexpr mint operator / (const mint& r) const { return mint(*this) /= r; } constexpr bool operator == (const mint& r) const { return _v == r._v; } constexpr bool operator != (const mint& r) const { return _v != r._v; } friend istream& operator >> (istream& is, mint& x) { long long t; is >> t; x = mint(t); return is; } friend ostream& operator << (ostream& os, const mint& x) { return os << x._v; } }; using mint = StaticModint<998244353>; // using mint = StaticModint<1000000007>; // 0 1 2 3 4 // → → - // → - - // → - → string c[5] = { "z1o-2", "z1o--", "z1o2-", "z--2-", "--o-2" }; int cost(int f, int t, bool b) { if(c[f][t] == '-') return 1e9; if(c[f][t] == 'z') return b; if(c[f][t] == 'o') return !b; return c[f][t] - '0'; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N, K; cin >> N >> K; vector<vector<vector<mint>>> dp(N, vector<vector<mint>> (K + 1, vector<mint>(5, 0))); dp[0][0][0] = 1; for(int i = 1; i < N; i++) { for(int j = 0; j <= K; j++) { for(int f = 0; f < 5; f++) { for(int t = 0; t < 5; t++) { int nj = j + cost(f, t, i & 1); if(nj > K) continue; dp[i][nj][t] += dp[i - 1][j][f]; } } } } if(N & 1) { mint ans = 0; for(int k = 0; k <= K; k++) { for(int i : {0, 1, 2, 4}) { ans += dp[N - 1][k][i]; } } cout << ans << "\n"; } else { mint ans = 0; for(int k = 0; k <= K; k++) { for(int i : {0, 1, 2, 3}) { ans += dp[N - 1][k][i]; } } cout << ans << "\n"; } return 0; }