結果
問題 |
No.3096 Snake Path
|
ユーザー |
|
提出日時 | 2025-04-08 19:23:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 5,618 bytes |
コンパイル時間 | 2,897 ms |
コンパイル使用メモリ | 214,764 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-04-08 19:23:48 |
合計ジャッジ時間 | 4,487 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> using namespace std; long long mod = 998244353; //入力が必ず-mod<a<modの時. struct mint{ long long v = 0; mint(){} mint(int a){v = a<0?a+mod:a;} mint(long long a){v = a<0?a+mod:a;} mint(unsigned long long a){v = a;} long long val(){return v;} mint &operator=(const mint &b) = default; mint operator-() const {return mint(0)-(*this);} mint operator+(const mint b){return mint(v)+=b;} mint operator-(const mint b){return mint(v)-=b;} mint operator*(const mint b){return mint(v)*=b;} mint operator/(const mint b){return mint(v)/=b;} mint operator+=(const mint b){ v += b.v; if(v >= mod) v -= mod; return *this; } mint operator-=(const mint b){ v -= b.v; if(v < 0) v += mod; return *this; } mint operator*=(const mint b){v = v*b.v%mod; return *this;} mint operator/=(mint b){ if(b == 0) assert(false); int left = mod-2; while(left){if(left&1) *this *= b; b *= b; left >>= 1;} return *this; } mint operator++(){*this += 1; return *this;} mint operator--(){*this -= 1; return *this;} mint operator++(int){*this += 1; return *this;} mint operator--(int){*this -= 1; return *this;} bool operator==(const mint b){return v == b.v;} bool operator!=(const mint b){return v != b.v;} bool operator>(const mint b){return v > b.v;} bool operator>=(const mint b){return v >= b.v;} bool operator<(const mint b){return v < b.v;} bool operator<=(const mint b){return v <= b.v;} mint pow(long long n){ mint ret = 1,p = v; if(n < 0) p = p.inv(),n = -n; while(n){ if(n&1) ret *= p; p *= p; n >>= 1; } return ret; } mint inv(){return mint(1)/v;} }; void jury(int N){ vector<vector<bool>> G(3*N,vector<bool>(3*N)); for(int i=0; i<N; i++){ G.at(i*3).at(i*3+1) = true; G.at(i*3+1).at(i*3+2) = true; G.at(i*3+1).at(i*3) = true; G.at(i*3+2).at(i*3+1) = true; if(i < N-1){ G.at(i*3+2).at(i*3+3) = true,G.at(i*3+3).at(i*3+2) = true; } } vector<int> P(3*N); iota(P.begin(),P.end(),0); vector<int> J(2*N); long long c = 0; do{ if(P.at(0) != 0) break; int edge = 0,pos = 0; for(int i=0; ; i++){ int one = P.at(i),two = P.at(i+1); if(G.at(one).at(two) == false){ edge++; if(abs(one/3-two/3) != 1 || (one+two)%6 != 5){pos = i+2; edge = -1000; break;} } if(two == 3*N-1){pos = i+2; break;} } c++; if(edge >= 0) J.at(edge)++; sort(P.begin()+pos,P.end()); reverse(P.begin()+pos,P.end()); }while(next_permutation(P.begin(),P.end())); for(int i=1; i<2*N; i++) J.at(i) += J.at(i-1); for(auto v : J) cout << v << " "; cout << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,K; cin >> N >> K; if(K == 0){cout << 1 << endl; return 0;} //jury(N); vector<mint> dp1(K+1),dp2(K+1),dp3(K+1); vector<mint> back1(K+1),back3(K+1); vector<mint> hold1(K+1),hold3(K+1); dp1.at(K) = 1; for(int i=0; i<N-1; i++){ vector<mint> next1(K+1),next2(K+1),next3(K+1); mint add = 0; if(i%2 == 0){ for(int k=0; k<=K; k++){ dp1.at(k) += back1.at(k); if(k) dp3.at(k-1) += back3.at(k); add += back1.at(k); if(k) add += back3.at(k); } } else{ for(int k=0; k<=K; k++){ if(k) dp1.at(k-1) += back1.at(k); dp3.at(k) += back3.at(k); add += back3.at(k); if(k) add += back1.at(k); } } //cout << i+1 << " " << add << endl; if(i > 0){ for(int k=0; k<=K; k++){ if(k+2 <= K) back1.at(k) = back1.at(k+2); if(k+2 <= K) back3.at(k) = back3.at(k+2); back1.at(k) += hold1.at(k); back3.at(k) += hold3.at(k); hold1.at(k) = 0,hold3.at(k) = 0; } } if(i%2 == 0){ for(int k=0; k<=K; k++){ mint sum = dp1.at(k)+dp2.at(k)+dp3.at(k); if(k) next1.at(k-1) += sum,next2.at(k-1) += sum; next3.at(k) += sum; if(k-2 >= 0) hold1.at(k-2) += dp3.at(k),hold3.at(k-2) += dp1.at(k); } } else{ for(int k=0; k<=K; k++){ mint sum = dp1.at(k)+dp2.at(k)+dp3.at(k); next1.at(k) += sum; if(k) next2.at(k-1) += sum,next3.at(k-1) += sum; if(k-2 >= 0) hold1.at(k-2) += dp3.at(k),hold3.at(k-2) += dp1.at(k); } } dp1 = next1,dp2 = next2,dp3 = next3; } mint answer = 0; for(auto v : dp1) answer += v; for(auto v : dp2) answer += v; for(auto v : dp3) answer += v; mint add = answer; if(N%2){ for(auto v : back1) answer += v; for(auto v : hold3) answer += v; back3.at(0) = 0; for(auto v : back3) answer += v; back3.at(1) = 0; for(auto v : back3) answer += v; } else{ for(auto v : back3) answer += v; for(auto v : hold1) answer += v; back1.at(0) = 0; for(auto v : back1) answer += v; back1.at(1) = 0; for(auto v : back1) answer += v; } //cout << N << " " << answer-add << endl; cout << answer.v << endl; }