팰린드롬 덧셈

$F(x)=\sum_{i=0}^{N}c_ix^i$라 하자. $N=0$이면 $F$ 자체가 팰린드롬이므로 그대로 출력하면 된다. 이제 $N\ge1$이라고 하자.

길이가 각각 $N+1$, $N$인 계수열 $a_0,\cdots,a_N$과 $b_0,\cdots,b_{N-1}$을 만들고

$$g(x)=\sum_{i=0}^{N}a_ix^i,\qquad h(x)=\sum_{i=0}^{N-1}b_ix^i$$

라 하자. 먼저

$$a_0=a_N=c_N$$

으로 둔다. 그리고 $i=0,1,\cdots,\left\lfloor\frac{N-1}{2}\right\rfloor$에 대하여 다음을 순서대로 계산한다. 모든 계산은 $M$을 법으로 한다.

$$b_i=c_i-a_i,\qquad b_{N-1-i}=b_i,$$ $$a_{i+1}=c_{N-1-i}-b_i,\qquad a_{N-1-i}=a_{i+1}.$$

각 단계에서 $b$의 바깥쪽 두 계수와 그 다음 $a$의 바깥쪽 두 계수를 동시에 맞춘다. 따라서 반복이 끝나면 $a_i=a_{N-i}$가 모든 $i$에 대해 성립하여 $g$가 팰린드롬이고, $b_i=b_{N-1-i}$도 성립한다. 또한 각 계수를 직접 대입하면

$$F=g+h$$

가 성립한다.

$h=0$이면 $g$ 하나만 출력하면 된다. $h\ne0$이고 $b_0\ne0$이면 $b_{N-1}=b_0\ne0$이므로 $h$의 차수는 $N-1$이고, $h$ 자체가 팰린드롬이다. 이 경우 $g,h$ 두 개를 출력하면 된다.

남은 경우는 $h\ne0$이고 $b_0=0$인 경우이다. $b_k\ne0$인 가장 작은 $k$를 잡자. $b$의 대칭성 때문에 바깥쪽의 $k$개 계수는 양쪽 모두 $0$이고, $b_{N-1-k}=b_k\ne0$이다. 따라서

$$d=N-1-2k,$$ $$r(x)=\sum_{j=0}^{d}b_{j+k}x^j$$

로 두면 $r$은 0이 아닌 팰린드롬이고

$$h=x^kr$$

이다.

이제

$$s=r+x^kr$$

로 두자. $r$이 차수 $d$의 팰린드롬이므로 $s$의 계수열은 차수 $d+k$를 기준으로 대칭이다. 따라서 $s$도 팰린드롬이다. 또한 $-r$도 팰린드롬이고

$$s+(-r)=x^kr=h$$

이므로

$$F=g+s+(-r)$$

를 얻는다.

$g$의 최고차항 계수는 $c_N\ne0$이다. 두 번째 경우의 $h$는 최고차항 계수가 $b_0\ne0$이고, 마지막 경우의 $r,s,-r$ 역시 구성상 최고차항 계수가 0이 아니다. 따라서 출력하는 모든 다항식은 문제의 정의를 만족한다.

각 계수는 상수 번만 처리되므로 한 테스트 케이스의 시간 복잡도는 $O(N)$, 추가 메모리는 $O(N)$이다. 전체 입력에 대해서는 $O\!\left(\sum(N+1)\right)$이다. 이 과정은 덧셈과 뺄셈만 사용하므로 $M$이 소수일 필요가 없다.

Solution written by GPT5.6