합성곱 ($\mathbb{F}_{2^{64}}$)

$\mathbb{F} _ {2^{64}}$의 원소로 이루어진 수열 $a_0, a_1, ..., a_{N - 1}$과 $b_0, b_1, ..., b_{M - 1}$가 주어질 때, 다음과 같이 $\mathbb{F} _ {2^{64}}$의 원소로 이루어진 수열 $c_0, c_1, ..., c_{(N - 1) + (M - 1)}$를 계산한다:

$c_k = \sum_{i+j=k} a_ib_j$

$P(x) = x^{64} + x^4 + x^3 + x + 1 \in \mathbb{F}_2[x]$를 $\mathbb{F}_2$ 위의 차수가 $64$인 기약 다항식이라 하자. $\mathbb{F} _ {2^{64}}$는 몫환 $\mathbb{F}_2[x] / (P(x))$로 구성된다. $\mathbb{F} _ {2^{64}}$의 원소는 $P(x)$로 나눈 나머지로 유일하게 표현할 수 있다.

차수가 64보다 작은 $\mathbb{F}_2[x]$ 위의 다항식은 부호 없는 64-비트 정수와 자연스럽게 동일시할 수 있다. 대응하는 수의 $i$-번째 비트는 단항식 $x^i$가 다항식에 포함되어 있을 때, 그리고 그럴 때에만 설정된다. 이 문제에서는 입력과 출력 모두에 이 정수 표현을 사용한다.

제한 조건

• $1 \leq N, M \leq 524288$
• $0 \leq a_i, b_i < 2^{64}$

$N$ $M$
$a_0$ $a_1$ ... $a_{N-1}$
$b_0$ $b_1$ ... $b_{M-1}$

$c_0$ $c_1$ ... $c_{(N - 1) + (M - 1)}$

_mm_clmulepi64_si128 내장 함수를 사용하면 도움이 될 수 있다.