11385번 - 씽크스몰

많이 자란 정민이는 부모님이 시키는 유명한 학습지 씽크스몰을 해야 한다. 정민이가 이번에 배워야 하는 부분은 다항식의 곱셈이다. 하지만 정민이는 게임을 해야만 하기에, 여러분에게 점수를 줄 테니 다항식 f(x)와 다항식 g(x)를 곱해주는 프로그램을 작성해 달라고 한다.

첫 번째 줄에 다항식 f(x)의 차수 N (1 ≤ N ≤ 1,000,000)과 다항식 g(x)의 차수 M (1 ≤ M ≤ 1,000,000)이 공백을 사이로 두고 주어진다.

두 번째 줄에는 다항식 f(x)의 계수를 나타내는 N + 1개의 자연수 a₀, a₁, ..., a_N-1, a_N이 주어진다. f(x) = a₀ + a₁·x + a₂·x² + ... + a_N-1·x^N-1 + a_N·x^N이다. (1 ≤ a_i ≤ 1,000,000)

세 번째 줄에는 다항식 g(x)의 계수를 나타내는 M + 1개의 자연수 b₀, b₁, ..., b_M-1, b_M이 주어진다. g(x) = b₀ + b₁·x + b₂·x² + ... + b_M-1·x^M-1 + b_M·x^M이다. (1 ≤ b_i ≤ 1,000,000)

f(x) × g(x) = c₀ + c₁·x + c₂·x² + ... + c_L·x^L라고 하자.

첫 번째 줄에 c₀, c₁, ..., c_L의 값을 모두 xor한 값, 즉 c₀ ⊕ c₁ ⊕ ... ⊕ c_L을 출력한다. C/C++에서는 c[0] ^ c[1] ^ ... ^ c[L-1] ^ c[L]의 값을 구하면 된다.

xor 연산을 시행하는 이유는, c_i를 출력하기에는 그 양이 너무 많기 때문이며, 문제의 풀이에는 영향을 주지 않는다.

f(x) = 1 + 2x, g(x) = 3 + 2x, f(x) × g(x) = 3 + 8x + 4x²