시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 34 17 3 50.000%

문제

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

입력

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

두 번째 줄에는 다항식 f(x)의 계수를 나타내는 N + 1개의 자연수 a0, a1, ..., aN-1, aN이 주어진다. f(x) = a0 + a1·x + a2·x2 + aN-1·xN-1 + aN·xN이다. (1 ≤ ai ≤ 1,000,000)

세 번째 줄에는 다항식 g(x)의 계수를 나타내는 M + 1개의 자연수 b0, b1, ..., bM-1, bM이 주어진다. g(x) = b0 + b1·x + b2·x2 + bM-1·xM-1 + bM·xM이다. (1 ≤ bi ≤ 1,000,000)

출력

f(x) × g(x) = c0 + c1·x + c2·x2 + ... + cL·xL라고 하자.

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

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

 

예제 입력

1 1
1 2
3 2

예제 출력

15

힌트

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

출처

Contest > kriiicon > 제 3회 kriiicon ㅆ번