7345번 - 다항식의 나머지 연산 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 157 | 59 | 40 | 36.036% |
문제
계수가 0 또는 1로만 이루어지는 특수한 다항식들의 집합에 대해 생각해보자.
이 집합의 두 다항식을 더하는 방법은 다음과 같다.
- 우선, 두 다항식을 더한다.
- 결과 다항식의 각 계수를 2로 나눈 나머지를 각각의 계수에 대입한다.
이때, (0 + 0) mod 2 = 0, (0 + 1) mod 2 = 1, (1 + 0) mod 2 = 1, and (1 + 1) mod 2 = 0 이므로
결국 결과 다항식의 각 차수의 계수는 더하고자 했던 두 다항식의 계수에 대한 XOR 연산의 결과가 된다.
(x 6 + x4 + x2 + x + 1) + (x7 + x + 1) = x7 + x6 + x4 + x2
이제 뺄셈을 정의하는데, 뺄셈의 경우에도 덧셈과 같이 (0 - 0) mod 2 = 0, (0 - 1) mod 2 = 1, (1 - 0) mod 2 = 1, and (1 - 1) mod 2 = 0 이므로
덧셈과 뺄셈은 이 다항식들의 집합에 대해 동일한 의미를 지닌다. (계수 간의 XOR 연산이 새 다항식의 계수가 됨)
예시는 다음과 같다.
(x 6 + x4 + x2 + x + 1) - (x7 + x + 1) = x7 + x6 + x4 + x2
다음으로 곱셈을 정의하는데, 곱셈 또한 일반적인 다항식 간의 곱셈 연산을 한 뒤 각각의 계수를 2로 나눈 나머지를 취하면 된다.
(x 6 + x4 + x2 + x + 1) (x7+ x + 1) = x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1
두 다항식 f(x)와 g(x)의 곱을 h(x)로 나눈 나머지는 f(x)와 g(x)를 위와 같은 방법으로 곱한 뒤, h(x)로 나눈 나머지가 된다.
(x 6 + x4 + x2 + x + 1) (x7 + x + 1) modulo (x8 + x4 + x3 + x + 1) = x7 + x6 + 1
어떤 다항식의 최고차항의 차수를 degree, 줄여서 d라 하면, f(x), g(x), h(x)의 계수가 0 또는 1이므로 각 다항식은 정수 d+1과 길이 d+1인 비트스트링의 쌍으로 유일하게 표기할 수 있다. 다항식의 차수는 1000보다 작다.
예를 들어 x 7 + x6 + 1은 다음과 같이 표기된다.
8 1 1 0 0 0 0 0 1
이때, 8은 총 비트의 개수이며, 최고차항의 차수(7) + 1이다.
이제 위에서 설명한 성질을 만족하는 세 다항식 f(x), g(x), h(x)가 설명한 형식대로 주어지면 f(x)g(x) modulo h(x)를 계산하면 된다.
입력
입력은 여러 테스트 케이스로 이루어져 있다.
입력의 첫 줄에 테스트케이스의 수 T가 주어지며, 각 테스트 케이스마다 세 줄에 걸쳐 문제에서 설명한 형식대로 표기한 f(x), g(x), h(x)가 주어진다.
출력
각 테스트 케이스마다 한 줄에 f(x)g(x)를 h(x)로 나눈 나머지를 문제에서 설명한 형식대로 출력한다.
예제 입력 1
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
예제 출력 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
출처
ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Taejon 2001 C번
- 빠진 조건을 찾은 사람: leehosu01
- 문제를 번역한 사람: portableangel
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호