結果
問題 | No.1289 RNG and OR |
ユーザー |
![]() |
提出日時 | 2020-11-14 02:48:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 373 ms / 2,000 ms |
コード長 | 624 bytes |
コンパイル時間 | 339 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 106,240 KB |
最終ジャッジ日時 | 2024-07-22 22:40:31 |
合計ジャッジ時間 | 2,843 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
def zeta_bit(L0):k = (len(L0) - 1).bit_length()n = 1 << kL = L0[:] + [0] * (n - len(L0))for i in range(k):for j in range(n):if j >> i & 1:L[j] += L[j^(1<<i)]return Ldef popcount_parity(x):x ^= x >> 1x ^= x >> 2x ^= x >> 4x ^= x >> 8x ^= x >> 16return x & 1P = 998244353N = int(input())A = [int(a) for a in input().split()]iS = pow(sum(A), P - 2, P)B = zeta_bit([a * iS % P for a in A])ans = 0for i, b in enumerate(B[:-1]):ans += pow(B[-1] - b, P - 2, P) * (1 if popcount_parity(i) else -1)print(ans * (-1) ** N % P)