結果
問題 |
No.1901 bitwise xor convolution (characteristic 2)
|
ユーザー |
![]() |
提出日時 | 2025-03-20 18:49:03 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,533 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 82,740 KB |
実行使用メモリ | 805,916 KB |
最終ジャッジ日時 | 2025-03-20 18:50:25 |
合計ジャッジ時間 | 8,140 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 4 MLE * 1 -- * 2 |
ソースコード
def fwht(a): h = 1 n = len(a) while h < n: for i in range(0, n, 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 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.append(bits) B = [] for _ in range(size): bits = list(map(int, input[ptr:ptr + 32])) ptr += 32 B.append(bits) C = [[0] * 63 for _ in range(size)] for m in range(63): for p in range(max(0, m - 31), min(31, m) + 1): q = m - p if q < 0 or q >= 32: continue X = [A[i][p] for i in range(size)] Y = [B[j][q] for j in range(size)] x = X.copy() y = Y.copy() fwht(x) fwht(y) for i in range(size): x[i] *= y[i] fwht(x) mod = 1 << (n + 1) for i in range(size): val = x[i] % mod parity = (val >> n) & 1 if parity: C[i][m] ^= 1 for k in range(size): print(' '.join(map(str, C[k])) + ' ') if __name__ == '__main__': main()