結果
問題 | No.3117 Reversible Tile |
ユーザー |
|
提出日時 | 2025-04-19 17:38:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 3,000 ms |
コード長 | 1,586 bytes |
コンパイル時間 | 1,853 ms |
コンパイル使用メモリ | 199,496 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-04-19 17:38:20 |
合計ジャッジ時間 | 2,969 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int MOD = 998244353; long long modpow(long long a, long long e=MOD-2) { long long r=1; while(e){ if(e&1) r = r*a % MOD; a = a*a % MOD; e >>= 1; } return r; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<int> A(N+2, 0); for(int i=1;i<=N;i++) cin >> A[i]; int K = N + 1; vector<int> D(K+1); D[1] = A[1]; for(int i=2;i<=N;i++) D[i] = A[i] ^ A[i-1]; D[N+1] = A[N]; int h = accumulate(D.begin()+1, D.begin()+K+1, 0); vector<long long> fact(K+1,1), ifact(K+1,1); for(int i=1;i<=K;i++) fact[i]=fact[i-1]*i%MOD; ifact[K] = modpow(fact[K]); for(int i=K;i>0;i--) ifact[i-1]=ifact[i]*i%MOD; auto C = [&](int n,int k)->long long { if(k<0||k>n) return 0; return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD; }; vector<long long> a(h+1), b(K-h+1), T(K+1); for(int u=0;u<=h;u++){ a[u] = C(h,u) * ( (u&1)? MOD-1 : 1 ) % MOD; } for(int v=0;v<=K-h;v++){ b[v] = C(K-h, v); } for(int u=0;u<=h;u++){ if(a[u]==0) continue; for(int v=0;v<=K-h;v++){ T[u+v] = (T[u+v] + a[u]*b[v]) % MOD; } } long long inv2 = (MOD+1)/2; vector<long long> X(K+1); for(int w=0;w<=K;w++){ long long S = (long long)(K - 2*w) % MOD; long long num = (S*S % MOD - K + MOD) % MOD; X[w] = num * inv2 % MOD; } long long ans = 0; for(int w=0;w<=K;w++){ long long term = modpow(X[w], M) * T[w] % MOD; ans = (ans + term) % MOD; } ans = ans * modpow(inv2, K) % MOD; cout << ans << "\n"; return 0; }