#1065668 (C++17) No.3096 Snake Path

• 問題: No.3096 Snake Path
• ユーザー: GOTKAKO
• 提出日時: 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;
}