Time Limit: 3s
Memory Limit: 128MB
계수가 0과 1뿐인 다항식을 생각해보자. 이런 다항식에서 두 다항식의 합은 평범한 다항식과는 동작이 다르다. 계수의 결과값을 modulo 2를 취한 값으로 나타내는 것이다. 즉, (0+0) = 0, (0+1) = 1, (1+0) = 1, (1+1) = 0 이 된다. 예를 들어보자.
(x6 + x4 + x2 + x + 1) + (x7 + x + 1) = x7 + x6 + x4 + x2
다항식의 뺄셈은 덧셈이랑 비슷하다. 계수를 뺄셈한 결과물에서 modulo 2를 취한 값을 계수로 사용하면 된다. 예를 들어보자.
(x6 + x4 + x2 + x + 1) - (x7 + x + 1) = x7 + x6 + x4 + x2
다항식의 곱셈은 일반적인 다항식의 곱셈이랑 다를게 없다. 다만 결과물의 계수가 modulo 2를 취한 값이여하한다.
(x6 + x4 + x2 + x + 1)(x7 + x + 1) = x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1
다항식 f(x)의 modulo h(x) 결과값은 f(x)를 h(x)로 나눈 나머지 다항식을 나타낸다.
(x6 + x4 + x2 + x + 1)(x7 + x + 1) modulo (x8 + x4 + x3 + x + 1) = x7 + x6 + 1
다항식에서 차수란, 계수가 1인 x의 지수값 중 가장 큰 수를 뜻한다. 예를 들어 x7 + x6 + 1 의 차수는 7이다.
자 이제 길고 긴 설명충 타임이 끝났다. 우리가 구할 것은, 3개의 다항식 f(x), g(x), h(x)가 주어졌을 때, f(x)g(x) modulo h(x)를 구해보자.
(단, f(x), g(x)의 차수는 h(x)의 차수보다 작고, h(x)의 차수는 1000보다 작다.)
컴퓨터로 다항식을 표현하는 것은 어려운 일이므로, 우리는 차수가 d인 다항식을 차수+1인 d+1와 각 차수별 계수 d+1개의 숫자를 이용해서 나타낼 것이다. 예를 들어 x7 + x6 + 1 는 다음과같이 나타낸다.
8 1 1 0 0 0 0 0 1
첫째줄에 테스트케이스의 개수 t가 입력으로 들어온다.
이후 각 테스트케이스마다 3개의 줄이 입력으로 들어온다.
각 줄은 f(x), g(x), 그리고 h(x)를 나타내는 정보이며, 다항식은 위에서 설명한표기방식대로 표현된다. 계수로 사용된 수는 0 또는 1뿐이다.
각 테스트케이스마다 한줄에 하나씩 f(x)g(x) modulo h(x) 결과를 출력한다. 결과 출력방식 역시 위의 표기방식을 따른다. 답이 0이 되는 경우는 없다고 가정해도 좋다.
각 줄의 마지막에는 불필요한 공백이 있어서는 안된다.
2 7 1 0 1 0 1 1 1 8 1 0 0 0 0 0 1 1 9 1 0 0 0 1 1 0 1 1 10 1 1 0 1 0 0 1 0 0 1 12 1 1 0 1 0 0 1 1 0 0 1 0 15 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1
8 1 1 0 0 0 0 0 1 14 1 1 0 1 1 0 0 1 1 1 0 1 0 0