結果
問題 | No.1289 RNG and OR |
ユーザー |
![]() |
提出日時 | 2020-08-26 09:13:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,217 bytes |
コンパイル時間 | 1,909 ms |
コンパイル使用メモリ | 67,968 KB |
最終ジャッジ日時 | 2025-01-13 14:56:54 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 4 WA * 17 |
ソースコード
#include <iostream> using namespace std; typedef long long ll; ll mod = 998244353,a[300010],b[300010],sum = 0; ll pw(ll a,ll x){ a %= mod; ll ret = 1; while(x){ if(x&1) (ret *= a) %= mod; x /= 2; (a *= a) %= mod; } return ret; } int main(){ int i,j,n; cin >> n; if(n>18) exit(1); for(i=0;i<(1<<n);i++) cin >> a[i]; for(i=0;i<(1<<n);i++){ b[i] = a[i]; (sum += a[i]) %= mod; } for(i=0;i<(1<<n);i++){ for(j=0;j<n;j++){ if(i & (1<<j)) (a[i] += a[i^(1<<j)]) %= mod; } } sum = pw(sum,mod - 2); for(i=0;i<(1<<n);i++) a[i] = pw((mod + 1 - a[i]*sum%mod),2*mod - 4); for(i=0;i<(1<<n);i++){ for(j=0;j<n;j++){ if(i & (1<<j)) (a[i] += (mod - 1)*a[i^(1<<j)]%mod) %= mod; } } for(i=0;i<(1<<n);i++){ for(j=0;j<n;j++){ if(i & (1<<j)) (b[i^(1<<j)] += b[i]) %= mod; } } for(i=0;i<(1<<n);i++) (b[i] *= sum) %= mod; ll ans = 0; for(i=0;i<(1<<n) - 1;i++) (ans += b[i^((1<<n) - 1)]*a[i]%mod) %= mod; /*for(i=0;i<(1<<n);i++){ cout << i << " " << b[i^((1<<n) - 1)]*10%mod << " " << a[i]*9%mod << endl; }*/ cout << ans << endl; }