#1161429 (C++23) No.3515 Anti EIKO

• 問題: No.3515 Anti EIKO
• ユーザー: 児童養護施設
• 提出日時: 2026-04-24 22:30:38
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 222 ms / 2,000 ms
• コード長: 2,772 bytes
• コンパイル時間: 2,625 ms
• コンパイル使用メモリ: 342,352 KB
• 実行使用メモリ: 7,972 KB
• 最終ジャッジ日時: 2026-04-24 22:30:49
• 合計ジャッジ時間: 7,095 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge4_1

ファイルパターン	結果
sample	AC * 3
other	AC * 31

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F>bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F>bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);

template<int mod=998244353> struct modint {
    int x;
    constexpr modint(long long x_=0):x(((x_%mod)+mod)%mod){}
    constexpr modint operator-(){
        auto res=*this;
        res.x=(x?mod-x:0);
        return res;
    }
    constexpr modint& operator+=(modint r){
        if((x+=r.x)>=mod) x-=mod;
        return *this;
    }
    constexpr modint& operator-=(modint r){
        if((x-=r.x)<0) x+=mod;
        return *this;
    }
    constexpr modint& operator*=(modint r){
        x=1ll*x*r.x%mod;
        return *this;
    }
    constexpr modint& operator/=(modint r){return *this*=r.inv();}
    constexpr friend modint operator+(modint a,modint b){return a+=b;}
    constexpr friend modint operator-(modint a,modint b){return a-=b;}
    constexpr friend modint operator*(modint a,modint b){return a*=b;}
    constexpr friend modint operator/(modint a,modint b){return a/=b;}
    constexpr modint inv() const {return pow(mod-2);}
    constexpr modint pow(long long b) const {
        assert(0<=b);
        modint a=*this,c=1;
        while(b){
            if(b&1) c*=a;
            a*=a;
            b>>=1;
        }
        return c;
    }
    constexpr int val() const {return x;}
    constexpr friend ostream& operator<<(ostream& os,const modint& m){return os<<m.val();}
    constexpr friend istream& operator>>(istream& is,modint& m){
        long long v;
        is>>v;
        m=modint(v);
        return is;
    }
};
using mint=modint<>;

template <class T>
vector<vector<T>> mat_mul(vector<vector<T>> a,vector<vector<T>> b){
    vector ret(si(a),vector<T>(si(b[0]),0));
    rep(i,si(a)){
        rep(j,si(b[0])){
            rep(k,si(b)){
                ret[i][j]+=a[i][k]*b[k][j];
            }
        }
    }
    return ret;
}

template <class T>
vector<vector<T>> mat_pow(vector<vector<T>> a,long k){
    vector ret(si(a),vector<T>(si(a),0));
    rep(i,si(a)) ret[i][i]=1;
    while(k>0){
        if(k&1) ret=mat_mul(a,ret);
        a=mat_mul(a,a);
        k>>=1;
    }
    return ret;
}

int main(){
    int N;
    long K;
    cin>>N>>K;
    N*=4;
    vector G(N+1,vector<mint>(N+1,0));
    rep(i,N){
        G[i][i+1]=mint(1)/5;
        if(i%4!=0){
            G[i][0]=mint(3)/5;
            G[i][1]=mint(1)/5;
        }
        else{
            G[i][0]=mint(4)/5;
        }
    }
    vector A=mat_pow(G,K);
    cout<<A[0][N]<<"\n";
}