G - OR Sum Editorial by MMNMM
定数倍の軽い解法離散フーリエ変換とその逆変換は線形な変換なので、和や定数倍は変換・逆変換と行う順番を交換することができます。
この問題では、長さ \(N\) の巡回畳み込みを \(d\coloneqq\left\lfloor\log _ 2\max\{1,A _ i,B _ i\}\right\rfloor+1\) 回行い、その結果を定数倍して合計します。 巡回畳み込みは離散フーリエ変換→各点積→離散フーリエ逆変換を行うことで求められるので、長さ \(N\) の離散フーリエ変換・逆変換が \(3d\) 回行われます。
ここで、離散フーリエ逆変換の前に定数倍と合計をしてしまうことで、長さを変えずに離散フーリエ変換・逆変換の回数を \(2d+1\) 回とすることができます。
実装例は以下のようになります。
離散フーリエ変換に numpy.fft.fft
を用いています。
from numpy import fft, around
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
d = max(1, max(A), max(B)).bit_length()
# ビットごとに分解
A_bit = [[(~a >> i) & 1 for a in A] for i in range(d)]
B_bit = [[(~b >> i) & 1 for b in reversed(B)] for i in range(d)]
# FFT の結果をかけて定数倍して足してから IFFT
# 結果(複素数)を整数にキャスト
AxB = around(fft.ifft(sum(fft.fft(a) * fft.fft(b) * (1 << i) for i, (a, b) in enumerate(zip(A_bit, B_bit))))).astype('int32')
print(((1 << d) - 1) * N - min(AxB))
posted:
last update: