結果

問題 No.3117 Reversible Tile
コンテスト
ユーザー Yu_212
提出日時 2025-04-19 09:39:07
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 90 ms / 3,000 ms
コード長 4,374 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,270 ms
コンパイル使用メモリ 283,324 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-19 09:39:14
合計ジャッジ時間 5,617 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

const int iinf = 1e9;
const ll inf = 1e18;
template<ll mod>
struct Mint {
    using M=Mint; ll v;
    M& put(ll x) { v=(x<mod)?x:x-mod; return *this; }
    Mint(ll x=0) { put(x%mod+mod); }
    M operator+(M m) {return M().put(v+m.v);}
    M operator-(M m) {return M().put(v+mod-m.v);}
    M operator*(M m) {return M().put(v*m.v%mod);}
    M operator/(M m) {return M().put(v*m.inv().v%mod);}
    M operator+=(M m) { return put(v+m.v); }
    M operator-=(M m) { return put(v+mod-m.v); }
    M operator*=(M m) { return put(v*m.v%mod); }
    M operator/=(M m) { return put(v*m.inv().v%mod); }
    bool operator==(M m) { return v==m.v; }
    M pow(ll m) const {
        M x=v, res=1;
        while (m) {
            if (m&1) res=res*x;
            x=x*x; m>>=1;
        }
        return res;
    }
    M inv() { return pow(mod-2); }
};
template<ll mod>
ostream&operator<<(ostream&o,Mint<mod>v){return o<<v.v;}


template<typename T>
ostream& operator<<(ostream &o, vector<T> v) {
    for (int i = 0; i < v.size(); i++)
        o << v[i] << (i+1<v.size()?" ":"");
    return o;
}
template <typename T>
struct SegTree {
    using F = function<T(T, T)>;
    int n;
    F f;
    T ti;
    vector<T> dat;
    SegTree() {}
    SegTree(F f, T ti,int num) : f(f), ti(ti) {
        n = max(__bit_ceil(num), 1);
        dat.assign(n << 1, ti);
    }
    SegTree(F f,T ti,vector<T>&v):SegTree(f,ti,v.size()){
        for (int i = 0; i < v.size(); i++)
            dat[n + i] = v[i];
        for(int i=n-1;i;i--) dat[i]=f(dat[i*2], dat[i*2+1]);
    }
    void set_val(int k, T x) {
        dat[k += n] = x;
        while(k >>= 1) dat[k] = f(dat[k*2], dat[k*2+1]);
    }
    T query(int a, int b) {
        if (a >= b) return ti;
        T vl = ti, vr = ti;
        for (int l=a+n, r=b+n; l<r; l>>=1, r>>=1) {
            if (l & 1) vl = f(vl, dat[l++]);
            if (r & 1) vr = f(dat[--r], vr);
        }
        return f(vl, vr);
    }
};
struct Edge { int to; ll cost; };

const int MOD = 998244353;

// a^e mod
ll modpow(ll a, ll e=MOD-2){
    ll r=1;
    while(e){
        if(e&1) r=r*a%MOD;
        a=a*a%MOD;
        e>>=1;
    }
    return r;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int N, M;
    cin >> N >> M;
    vector<int> A(N+1);
    for(int i=1;i<=N;i++){
        cin >> A[i];
    }

    // DP[i&1][t][p]: 長さ i まで見て、
    //  prefix-zero の回数が t, 現在の prefix-parity が p(0 or 1)
    //  となる y_1..y_i の (-1)^{y·A} の総和
    vector< vector<array<ll,2>> >
        dp(2, vector<array<ll,2>>(N+2, {0,0}));
    dp[0][1][0] = 1;  // i=0: prefix[0]=0 なのでゼロ回数=1, parity=0

    for(int i=1;i<=N;i++){
        auto &cur = dp[(i-1)&1];
        auto &nxt = dp[i&1];
        // clear
        for(int t=1;t<=i+1;t++) nxt[t][0]=nxt[t][1]=0;

        // 遷移
        // y_i = 0: prefix は変わらず p, new_t = t + (p==0), weight = +1
        // y_i = 1: prefix flips to 1-p, new_t = t + ((1-p)==0),
        //           weight = (-1)^{A_i}
        ll w1 = (A[i]==1 ? MOD-1 : 1);

        for(int t=1;t<=i;t++){
            for(int p=0;p<2;p++){
                ll v = cur[t][p];
                if(!v) continue;
                // case y=0
                int np = p;
                int nt = t + (np==0);
                nxt[nt][np] = (nxt[nt][np] + v) % MOD;
                // case y=1
                np = 1-p;
                nt = t + (np==0);
                nxt[nt][np] = (nxt[nt][np] + v * w1) % MOD;
            }
        }
        // swap done by toggling i&1
    }

    // C[t] = dp[N&1][t][0] + dp[N&1][t][1]
    vector<ll> C(N+2,0);
    for(int t=1;t<=N+1;t++){
        C[t] = (dp[N&1][t][0] + dp[N&1][t][1]) % MOD;
    }

    // 2^{-N} mod
    ll inv2 = (MOD+1)/2;
    ll inv2N = modpow(inv2, N);

    // 前半 P = N(N+1)/2 mod
    ll P = (ll)N * (N+1) % MOD * modpow(2) % MOD;

    // T(t) = 2*(t^2 - (N+1)t) + P
    auto T = [&](int t)->ll{
        ll tt = ( (ll)t * t % MOD - (ll)(N+1) * t % MOD + MOD ) % MOD;
        return ( (2*tt)%MOD + P ) % MOD;
    };

    ll ans = 0;
    for(int t=1;t<=N+1;t++){
        if(C[t]==0) continue;
        ll w = modpow(T(t), M);
        ans = (ans + C[t] * w) % MOD;
    }

    // 最後に 2^{-N} をかけて完成
    ans = ans * inv2N % MOD;
    cout << ans << "\n";

    return 0;
}
0