結果

問題 No.1901 bitwise xor convolution (characteristic 2)
ユーザー lam6er
提出日時 2025-03-31 18:00:21
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,243 bytes
コンパイル時間 200 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 270,600 KB
最終ジャッジ日時 2025-03-31 18:01:28
合計ジャッジ時間 7,096 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

def readints():
    return list(map(int, sys.stdin.readline().split()))

def fwht(a, n):
    size = 1 << n
    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 *= 2

def inverse_fwht(a, n):
    size = 1 << n
    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) // 2
                a[j + h] = (x - y) // 2
        h *= 2

def main():
    n = int(sys.stdin.readline())
    size = 1 << n

    # Read A
    A = []
    for _ in range(size):
        bits = list(map(int, sys.stdin.readline().split()))
        val = 0
        for i in range(32):
            if bits[i]:
                val |= 1 << i
        A.append(val)

    # Read B
    B = []
    for _ in range(size):
        bits = list(map(int, sys.stdin.readline().split()))
        val = 0
        for i in range(32):
            if bits[i]:
                val |= 1 << i
        B.append(val)

    # Preprocess A_m and B_n
    a_m = []
    for m in range(32):
        tmp = [0] * size
        for i in range(size):
            tmp[i] = (A[i] >> m) & 1
        a_m.append(tmp.copy())
        fwht(a_m[m], n)

    b_n = []
    for m in range(32):
        tmp = [0] * size
        for i in range(size):
            tmp[i] = (B[i] >> m) & 1
        b_n.append(tmp.copy())
        fwht(b_n[m], n)

    C = [0] * size

    for m in range(32):
        for m_prime in range(32):
            l = m + m_prime
            if l >= 63:
                continue

            product = [a_m[m][i] * b_n[m_prime][i] for i in range(size)]

            # Inverse FWHT
            inverse_fwht(product, n)

            for k in range(size):
                bit = (product[k] % 2 + 2) % 2
                if bit:
                    C[k] ^= (1 << l)

    # Output the result
    for k in range(size):
        output = [0] * 63
        for l in range(63):
            output[l] = (C[k] >> l) & 1
        print(' '.join(map(str, output)))

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