結果
問題 |
No.1753 Don't cheat.
|
ユーザー |
![]() |
提出日時 | 2021-06-20 00:28:12 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,042 bytes |
コンパイル時間 | 387 ms |
コンパイル使用メモリ | 82,288 KB |
実行使用メモリ | 91,540 KB |
最終ジャッジ日時 | 2024-12-31 18:27:44 |
合計ジャッジ時間 | 133,733 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | TLE * 2 |
other | TLE * 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 << 11 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)