結果

問題 No.1289 RNG and OR
ユーザー lam6er
提出日時 2025-03-20 21:15:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 461 ms / 2,000 ms
コード長 1,235 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 127,800 KB
最終ジャッジ日時 2025-03-20 21:15:44
合計ジャッジ時間 2,524 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx + (1 << N)]))
    idx += (1 << N)
    
    size = 1 << N
    g = [0] * size
    
    for t in range(size):
        g[t] = A[t] % MOD
    
    # Compute Zeta transform for sum over subsets
    for i in range(N):
        for mask in range(size):
            if mask & (1 << i):
                g[mask] = (g[mask] + g[mask ^ (1 << i)]) % MOD
    
    S_total = sum(A) % MOD
    inv_S_total = pow(S_total, MOD-2, MOD) if S_total != 0 else 0
    
    full_mask = (1 << N) - 1
    total = 0
    
    for S in range(1, size):
        k = bin(S).count('1')
        mask_t = full_mask ^ S
        f_S = g[mask_t]
        Q_S = (f_S * inv_S_total) % MOD
        denominator = (1 - Q_S) % MOD
        if denominator == 0:
            continue  # problem statement ensures this does not happen
        denominator_inv = pow(denominator, MOD-2, MOD)
        if k % 2 == 0:
            term = (MOD - 1) * denominator_inv % MOD
        else:
            term = denominator_inv % MOD
        total = (total + term) % MOD
    
    print(total)
    
if __name__ == '__main__':
    main()
0