結果
問題 | No.1753 Don't cheat. |
ユーザー |
![]() |
提出日時 | 2021-06-20 00:37:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,174 ms / 3,000 ms |
コード長 | 1,042 bytes |
コンパイル時間 | 448 ms |
コンパイル使用メモリ | 82,832 KB |
実行使用メモリ | 76,864 KB |
最終ジャッジ日時 | 2024-12-31 18:31:30 |
合計ジャッジ時間 | 39,079 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
MOD = 998244353 def fwht(a) -> None: n = len(a) i = 1 while i < n: for j in range(n): if (j & i) == 0: x, y = a[j], a[j | i] a[j] = (x + y) % MOD a[j | i] = (x - y) % MOD i *= 2 def ifwht(a) -> None: inv_2 = pow(2, MOD - 2, MOD) n = len(a) i = 1 while i < n: for j in range(n): if (j & i) == 0: x, y = a[j], a[j | i] a[j] = (x + y) * inv_2 % MOD a[j | i] = (x - y) * inv_2 % MOD i *= 2 sz = 1 << 10 n = int(input()) a = list(map(int, input().split())) while len(a) < sz: a.append(0) s = sum(a) sinv = pow(s, MOD - 2, MOD) f = [0 for i in range(sz)] f[0] = 1 for i in range(1, sz): f[i] = -a[i] * sinv % MOD res = 0 for x in range(1, sz): g = f.copy() g[x] = 0 fwht(g) for i in range(len(g)): g[i] = pow(g[i], MOD - 2, MOD) ifwht(g) res += g[x] res %= MOD res *= a[0] res %= MOD res *= sinv res %= MOD print(res)