結果

問題 No.3117 Reversible Tile
ユーザー keigo kuwata
提出日時 2025-04-24 14:59:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,911 bytes
コンパイル時間 2,002 ms
コンパイル使用メモリ 195,896 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-04-24 14:59:46
合計ジャッジ時間 5,333 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 4 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
inline int add(int a, int b){ a+=b; if(a>=MOD) a-=MOD; return a; }
inline int mul(long long a, long long b){ return (int)(a*b%MOD); }
int mod_pow(int a, long long e=MOD-2){
    long long r=1, x=a;
    while(e){
        if(e&1) r=r*x%MOD;
        x=x*x%MOD;
        e>>=1;
    }
    return (int)r;
}

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

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

    // 差分 d を求める
    vector<int> d(N+2, 0);
    d[1] = A[1];
    for(int i=2;i<=N;i++){
        d[i] = A[i] ^ A[i-1];
    }
    d[N+1] = A[N];

    // 偶奇和が偶数でなければ 0
    int s = 0;
    for(int i=1;i<=N+1;i++) s += d[i];
    if(s % 2){
        cout << 0 << "\n";
        return 0;
    }
    // s は奇頂点数
    // DP の準備
    int V = N+1;
    int inv2 = mod_pow(2);

    auto C2 = [&](int x){
        // xC2 mod
        return mul( (long long)x*(x-1)%MOD, (long long)inv2 );
    };

    vector<int> dp_prev(V+1, 0), dp_cur(V+1, 0);
    dp_prev[0] = 1;

    for(int step=0; step<M; step++){
        fill(dp_cur.begin(), dp_cur.end(), 0);
        for(int r=0; r<=V; r++){
            int ways = dp_prev[r];
            if(!ways) continue;
            int e = V - r;
            // 両方偶 -> r+2
            if(e >= 2){
                int c = C2(e);
                dp_cur[r+2] = add(dp_cur[r+2], mul(ways, c));
            }
            // 両方奇 -> r-2
            if(r >= 2){
                int c = C2(r);
                dp_cur[r-2] = add(dp_cur[r-2], mul(ways, c));
            }
            // 片方ずつ -> r
            long long cross = (long long)r * e % MOD;
            dp_cur[r] = add(dp_cur[r], mul(ways, cross));
        }
        swap(dp_prev, dp_cur);
    }

    cout << dp_prev[s] << "\n";
    return 0;
}
0