結果

問題 No.985 Hadamard
ユーザー lam6er
提出日時 2025-03-20 11:44:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 248 ms / 2,000 ms
コード長 1,127 bytes
コンパイル時間 671 ms
コンパイル使用メモリ 82,124 KB
実行使用メモリ 189,412 KB
最終ジャッジ日時 2025-03-20 11:44:47
合計ジャッジ時間 7,676 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    size = 1 << N
    
    C = list(map(int, input[ptr:ptr+size]))
    ptr += size
    
    L = []
    H = []
    for _ in range(size):
        L.append(int(input[ptr]))
        H.append(int(input[ptr+1]))
        ptr += 2
    
    # Check if any L[i] > H[i]
    for i in range(size):
        if L[i] > H[i]:
            print(-1)
            return
    
    # Perform FWT on C to get D
    a = C.copy()
    h = 1
    while h < size:
        for i in range(0, size, h*2):
            for j in range(i, i + h):
                x = a[j]
                y = a[j + h]
                a[j] = x + y
                a[j + h] = x - y
        h <<= 1
    D = a
    
    sum_total = 0
    for i in range(size):
        d = D[i]
        if d > 0:
            sum_total += d * H[i]
        elif d < 0:
            sum_total += d * L[i]
    
    inv_2n = pow(2, N, MOD)
    inv_2n = pow(inv_2n, MOD - 2, MOD)
    
    ans = (sum_total % MOD) * inv_2n % MOD
    print(ans)

if __name__ == "__main__":
    main()
0