(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

View problem - 씽크스몰 (kriii3_TT)

Time limitMemory limit# of submissions# of submitted usersSolved #Accepted user ratio
10000 ms512 MiB108211361.90%

많이 자란 정민이는 부모님이 시키는 유명한 학습지 씽크스몰을 해야 한다. 정민이가 이번에 배워야 하는 부분은 다항식의 곱셈이다. 하지만 정민이는 게임을 해야만 하기에, 여러분에게 점수를 줄 테니 다항식 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이다.

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

출력

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

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

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

부분문제

부분문제 점수 N, M ai, bi
1 10 ≤ 1,000 ≤ 100
2 10 ≤ 100,000 ≤ 100
3 10 ≤ 1,000,000 ≤ 1,000,000

입출력 예제

<tr><td><samp>1 1<br/>1 2<br/>3 2</samp></td><td><samp>15</samp></td></tr></tbody>
입력 예시 출력 예시

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