結果

問題 No.1901 bitwise xor convolution (characteristic 2)
ユーザー gew1fw
提出日時 2025-06-12 16:47:44
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,077 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 753,688 KB
最終ジャッジ日時 2025-06-12 16:48:21
合計ジャッジ時間 7,178 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 TLE * 1 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

def fwht(arr, n, invert=False):
    m = 1
    while m < n:
        for i in range(0, n, m * 2):
            for j in range(i, i + m):
                x = arr[j]
                y = arr[j + m]
                arr[j] = x + y
                arr[j + m] = x - y
                if invert:
                    arr[j] >>= 1
                    arr[j + m] >>= 1
        m <<= 1

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    size = 1 << n

    A = []
    for _ in range(size):
        bits = list(map(int, input[ptr:ptr+32]))
        ptr += 32
        a = 0
        for j in range(32):
            a |= (bits[j] << j)
        A.append(a)
    
    B = []
    for _ in range(size):
        bits = list(map(int, input[ptr:ptr+32]))
        ptr += 32
        b = 0
        for j in range(32):
            b |= (bits[j] << j)
        B.append(b)
    
    fwht_A = []
    for m in range(32):
        arr = [0] * size
        for i in range(size):
            arr[i] = (A[i] >> m) & 1
        fwht(arr, size, invert=False)
        fwht_A.append(arr)
    
    fwht_B = []
    for m in range(32):
        arr = [0] * size
        for i in range(size):
            arr[i] = (B[i] >> m) & 1
        fwht(arr, size, invert=False)
        fwht_B.append(arr)
    
    C = [0] * size
    
    for m in range(63):
        transformed = [0] * size
        for m_prime in range(32):
            m_double = m - m_prime
            if m_double < 0 or m_double >= 32:
                continue
            a = fwht_A[m_prime]
            b = fwht_B[m_double]
            for i in range(size):
                transformed[i] += a[i] * b[i]
        fwht(transformed, size, invert=True)
        for k in range(size):
            bit = transformed[k] % 2
            if bit:
                C[k] |= (1 << m)
    
    output = []
    for c in C:
        bits = []
        for j in range(63):
            bits.append(str((c >> j) & 1))
        output.append(' '.join(bits))
    print('\n'.join(output))

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