結果
問題 | No.985 Hadamard |
ユーザー |
|
提出日時 | 2020-02-11 15:15:45 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 1,225 bytes |
コンパイル時間 | 1,915 ms |
コンパイル使用メモリ | 163,044 KB |
実行使用メモリ | 16,000 KB |
最終ジャッジ日時 | 2024-11-30 16:22:58 |
合計ジャッジ時間 | 5,697 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>const int maxn = 1 << 18;typedef long long ll;const ll mo = 998244353;int n;ll c[maxn], d[maxn], l[maxn], h[maxn], b[maxn], a[maxn];ll mpow(ll u, ll k) {ll ans = 1;for(; k > 0; k >>= 1, u = u * u % mo) {if(k & 1) {ans = ans * u % mo;}}return ans;}void fwt(const ll *u, ll *v) {memcpy(v, u, sizeof(*u) * n);for(int d = 1; d < n; d *= 2)for(int i = 0; i < n; i += d * 2)for(int j = 0; j < d; ++j) {auto ui = v[i + j], uj = v[i + j + d];auto &vi = v[i + j], &vj = v[i + j + d];vi = (ui + uj);vj = (ui - uj);}}int main() {scanf("%d", &n);n = 1 << n;for(int i = 0; i < n; ++i) {scanf("%lld", c + i);}for(int i = 0; i < n; ++i) {scanf("%lld%lld", l + i, h + i);}fwt(c, d);for(int i = 0; i < n; ++i) {if(d[i] >= 0)b[i] = h[i];elseb[i] = l[i];}fwt(b, a);ll ans = 0ll;for(int i = 0; i < n; ++i)ans = (ans + (a[i] % mo) * (c[i] % mo) % mo) % mo;ans = ans * mpow(n, mo - 2) % mo;ans = (ans + mo) % mo;printf("%lld\n", ans);return 0;}