#P18618. Palindromic Polynomial

Palindromic Polynomial

Palindromic Polynomial

一个回文多项式是指系数从前往后与从后往前读取完全相同的非零多项式。

Alan 曾经有一个次数不超过 10410^4 的回文多项式 AA。他记录了它在 nn 个不同整数点处的值对 109+910^9+9 取模的结果,随后丢失了原多项式。请根据这些点,恢复任意一个符合条件的回文多项式;如果不存在,则报告无解。

形式化地,给定 (x1,y1),…,(xn,yn)(x_1,y_1),\ldots,(x_n,y_n),令 p=109+9p=10^9+9。求

A(x)=adxd+ad−1xd−1+⋯+a1x+a0A(x)=a_dx^d+a_{d-1}x^{d-1}+\cdots+a_1x+a_0

使得:

  • 0≤d≤1040\le d\le10^4,且 ad≠0a_d\ne0;
  • 对所有 0≤j≤d0\le j\le d,0≤aj<p0\le a_j<p;
  • 对所有 1≤i≤n1\le i\le n,A(xi)≡yi(modp)A(x_i)\equiv y_i\pmod p;
  • 对所有 0≤j≤d0\le j\le d,aj=ad−ja_j=a_{d-j}。

输入格式

第一行一个整数 tt(1≤t≤1001\le t\le100),表示测试用例数。

每个测试用例:

第一行一个整数 nn(1≤n≤10001\le n\le1000)。

第二行 nn 个互不相同的整数 x1,…,xnx_1,\ldots,x_n(0≤xi<109+90\le x_i<10^9+9)。

第三行 nn 个整数 y1,…,yny_1,\ldots,y_n(0≤yi<109+90\le y_i<10^9+9)。

同一输入文件中所有测试用例的 nn 之和不超过 10001000。

输出格式

对每个测试用例,若无解,输出一行 −1-1。

否则,第一行输出次数 dd;第二行按从常数项到最高次项的顺序输出 d+1d+1 个整数 a0,a1,…,ada_0,a_1,\ldots,a_d。

有多个解时输出任意一个。不需要最小化次数。

样例输入 1

8
2
0 1
2 4
3
0 1 2
2 10 36
4
0 1 2 3
1 4 9 16
5
0 1 2 3 4
1 25 961 14641 116281
2
2 500000005
5 375000004
2
2 500000005
5 375000004
2
2 500000005
1 2
3
2 500000005 3
5 375000004 10

样例输出 1

1
2 2
3
2 3 3 2
2
1 2 1
8
1 2 3 4 5 4 3 2 1
3
1 666666672 666666672 1
3
1 666666672 666666672 1
-1
-1

说明

一个次数为 dd 的多项式恰有 d+1d+1 个系数,内部系数可以为零,但最高次项系数不能为零。本题也不接受零多项式。

以下多项式是回文多项式:

  • 2x3+3x2+3x+22x^3+3x^2+3x+2,系数为 [2,3,3,2][2,3,3,2];
  • 5x4+10x2+55x^4+10x^2+5,系数为 [5,0,10,0,5][5,0,10,0,5];
  • x4+1x^4+1,系数为 [1,0,0,0,1][1,0,0,0,1];
  • 11,系数为 [1][1]。

以下多项式不是回文多项式:

  • 2x3+3x2+3x+12x^3+3x^2+3x+1,系数为 [1,3,3,2][1,3,3,2];
  • 2x4+3x3+3x2+2x2x^4+3x^3+3x^2+2x,系数为 [0,2,3,3,2][0,2,3,3,2];
  • x5+xx^5+x,系数为 [0,1,0,0,0,1][0,1,0,0,0,1]。

上述列表统一按本题输出要求从常数项向最高次项书写。不能通过在两端补零把原来不回文的多项式当作合法答案。