結果
問題 | No.1289 RNG and OR |
ユーザー |
![]() |
提出日時 | 2020-11-14 02:46:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 375 ms / 2,000 ms |
コード長 | 2,114 bytes |
コンパイル時間 | 237 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 106,112 KB |
最終ジャッジ日時 | 2024-07-22 22:40:04 |
合計ジャッジ時間 | 2,729 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
def or_convolution(A, B):n = max(len(A), len(B))X = [0] * (1 << (n - 1).bit_length())for i, a in enumerate(A):for j, b in enumerate(B):X[i|j] += a * breturn Xdef and_convolution(A, B):n = max(len(A), len(B))X = [0] * (1 << (n - 1).bit_length())for i, a in enumerate(A):for j, b in enumerate(B):X[i&j] += a * breturn Xdef 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 mobius_bit(L0): # zeta_bit の逆変換k = (len(L0) - 1).bit_length()n = 1 << kL = L0[:] + [0] * (n - len(L0))for i in range(k):for j in range(n)[::-1]:if j >> i & 1:L[j] -= L[j^(1<<i)]return Ldef zeta_bit_inv(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)[::-1]:if j >> i & 1:L[j^(1<<i)] += L[j]return Ldef mobius_bit_inv(L0): # zeta_bit_inv の逆変換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^(1<<i)] -= L[j]return Ldef popcount_parity(x):x ^= x >> 1x ^= x >> 2x ^= x >> 4x ^= x >> 8x ^= x >> 16return x & 1def r(a):for i in range(1, 10001):if i and a * i % P <= 10000:return str(a*i%P) + "/" + str(i)if i and -a * i % P <= 10000:return str(-(-a*i%P)) + "/" + str(i)return aP = 998244353N = int(input())A = [int(a) for a in input().split()]S = sum(A)iS = pow(S, P - 2, P)A = [a * iS % P for a in A]B = zeta_bit(A)ans = 0for i, b in enumerate(B[:-1]):if popcount_parity(i):ans += pow(B[-1] - b, P - 2, P)else:ans -= pow(B[-1] - b, P - 2, P)print(ans * (-1) ** N % P)