結果

問題 No.3117 Reversible Tile
コンテスト
ユーザー GOTKAKO
提出日時 2025-04-19 10:21:57
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,981 ms / 3,000 ms
コード長 4,450 bytes
コンパイル時間 2,518 ms
コンパイル使用メモリ 207,452 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-04-19 10:22:29
合計ジャッジ時間 29,152 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct Montgomery{
    //2^62未満&奇数modのみ.
    //初めにsetmodする.
    using u64 = uint64_t;
    using u128 = __uint128_t;
 
    private:
    static u64 mod,N2,Rsq; //N*N2≡1(mod N);
    //Rsq = R^2modN; R=2^64.
    u64 v = 0;
    public:
    long long val(){return reduce(v);}
    u64 getmod(){return mod;}
    static void setmod(u64 m){
        assert(m<(1LL<<62)&&(m&1));
        mod = m; N2 = mod;
        for(int i=0; i<5; i++) N2 *= 2-N2*mod;
        Rsq = (-u128(mod))%mod;
    }
    //reduce = T*R^-1modNを求める.
    u64 reduce(const u128 &T){
        //T*R^-1≡(T+(T*(-N2))modR*N)/R 2N未満なので-N必要かだけで良い.
        u64 ret = (T+u128(((u64)T)*(-N2))*mod)>>64;
        if(ret >= mod) ret -= mod;
        return ret;
    }
    //初期値<mod. 初めにw*R modN...->reduce(R^2)でok.
    Montgomery(){v = 0;} Montgomery(long long w):v(reduce(u128(w)*Rsq)){}
 
    Montgomery& operator=(const Montgomery &b) = default;
    Montgomery operator-()const{return Montgomery()-Montgomery(*this);}
    Montgomery operator+(const Montgomery &b)const{return Montgomery(*this)+=b;}
    Montgomery operator-(const Montgomery &b)const{return Montgomery(*this)-=b;}
    Montgomery operator*(const Montgomery &b)const{return Montgomery(*this)*=b;}
    Montgomery operator/(const Montgomery &b)const{return Montgomery(*this)/=b;}
    Montgomery& operator+=(const Montgomery &b){
        v += b.v;
        if(v >= mod) v -= mod;
        return (*this);
    }
    Montgomery& operator-=(const Montgomery &b){
        v += mod-b.v;
        if(v >= mod) v -= mod;
        return (*this);
    }
    Montgomery& operator*=(const Montgomery &b){
        v = reduce(u128(v)*b.v);
        return (*this);
    }
    Montgomery& operator/=(const Montgomery &b){
        (*this) *= b.inv();
        return (*this);
    }
    Montgomery pow(u64 b)const{
        Montgomery ret = 1,p = (*this);
        while(b){
            if(b&1) ret *= p;
            p *= p; b >>= 1;
        }
        return ret;
    }
    Montgomery inv()const{return pow(mod-2);}
 
    bool operator!=(const Montgomery &b){return v!=b.v;}
    bool operator==(const Montgomery &b){return v==b.v;}
};
typename Montgomery::u64 Montgomery::mod,Montgomery::N2,Montgomery::Rsq;
using mont = Montgomery;
using mint = Montgomery;

mint Val[5001];


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    mint::setmod(998244353);
    for(int i=1; i<=5000; i++) Val[i] = i;
    int N,M; cin >> N >> M;
    vector<int> A(N);
    for(auto &a : A) cin >> a;
    {
        auto B = A;
        for(int i=1; i<N; i++) B.at(i) ^= A.at(i-1);
        A = B;
    }

    vector<mint> X(N),Y(N); //Xi<-A0=0の時のA1~An-1の1sがi個となる総数,Yi<-A0=1の時.
    {
        int one = 0;
        for(int i=1; i<N; i++) one += A.at(i);
        if(A.at(0) == 0) X.at(one) = 1;
        else Y.at(one) = 1;
    }
    mint div2 = mint(1)/2;

    while(M--){
        vector<mint> nX(N),nY(N);
        for(int i=0; i<N; i++){
            if(X.at(i) == 0) continue;
            if(i) nY.at(i-1) += X.at(i)*Val[i]; //A0とA1~n-1で1->0.
            if(i < N-1) nY.at(i+1) += X.at(i)*Val[N-1-i]; //A0とA1~n-1で0->1.
            nY.at(i) += X.at(i); //A0とAn. (An->Ri=N-1の時にありうる 変化なし).
            
            if(i) nX.at(i-1) += X.at(i)*Val[i]; //A1~An-1 An.
            if(i < N-1) nX.at(i+1) += X.at(i)*Val[N-1-i];
            nX.at(i) += X.at(i)*i*(N-1-i); //0->1 1->0.
            if(i > 1) nX.at(i-2) += X.at(i)*Val[i]*Val[i-1]*div2; //0->1 x2.
            if(i < N-2) nX.at(i+2) += X.at(i)*Val[N-1-i]*Val[N-1-i-1]*div2; //1->0 x2.
        }
        for(int i=0; i<N; i++){
            if(Y.at(i) == 0) continue;
            if(i) nX.at(i-1) += Y.at(i)*Val[i]; //A0とA1~n-1で1->0.
            if(i < N-1) nX.at(i+1) += Y.at(i)*Val[N-1-i]; //A0とA1~n-1で0->1.
            nX.at(i) += Y.at(i); //A0とAn. (An->Ri=N-1の時にありうる 変化なし).
            
            if(i) nY.at(i-1) += Y.at(i)*Val[i]; //A1~An-1 An.
            if(i < N-1) nY.at(i+1) += Y.at(i)*Val[N-1-i];
            nY.at(i) += Y.at(i)*i*(N-1-i); //0->1 1->0.
            if(i > 1) nY.at(i-2) += Y.at(i)*Val[i]*Val[i-1]*div2; //0->1 x2.
            if(i < N-2) nY.at(i+2) += Y.at(i)*Val[N-1-i]*Val[N-1-i-1]*div2; //1->0 x2.
        }
        X = nX,Y = nY;
    }

    cout << X.at(0).val() << endl;
}
0