本题没有可用的提交语言。

#P1641. 有理逼近
ID: 642
远端评测题
1000ms
10MiB
难度: 6

描述

一个$n$次多项式$p(x)$可通过将其系数与函数$f(x)$在$x=0$处展开的幂级数的前$n$个系数匹配，来逼近$f(x)$。例如，

遗憾的是，多项式虽然“良好”，但在逼近行为不佳的函数（如具有奇点的函数）时效果不佳。为解决这一问题，我们可改用形如$p(x)/q(x)$的有理函数逼近，其中$p(x)$和$q(x)$均为多项式。Approximate Calculation Machinery公司请你解决此问题，以便将你的方案集成到他们的近似计算软件中。

给定$m$、$n$以及$f(x)$幂级数展开的前$m+n$个系数，我们希望计算两个多项式$p(x)$和$q(x)$，其次数分别不超过$m-1$和$n-1$，使得$q(x) \cdot f(x) - p(x)$的幂级数展开中，前$m+n-1$项的系数为$0$，且$x^{m+n-1}$项的系数为$1$。即，我们需要找到$p(x)$和$q(x)$使得：

其中$\dots$包含次数高于$m+n-1$的项。由此，$f(x)$可被$p(x)/q(x)$逼近。

背景定义

• $n$次多项式$p(x)$可表示为$p_0 + p_1x + p_2x^2 + \dots + p_nx^n$，本题中$p_i$为整数。
• $f(x)$在$0$处的幂级数展开可表示为$f_0 + f_1x + f_2x^2 + \dots$，本题中$f_i$为整数。

输入

输入包含多个测试用例。每个用例占一行，格式为 m n f0 f1 ... fm+n-1，其中$f_i$是$f(x)$幂级数展开中$x^i$项的系数。保证：

• $1 \leq m, 1 \leq n \leq 4$，$2 \leq m + n \leq 10$，且$|f_i| \leq 5$。
• 输入以m = n = 0的行结束，该行无$f$的系数。
• 给定输入存在唯一解。

输出

对每个测试用例，输出两行。第一行打印多项式$p(x)$，第二行打印$q(x)$。

• $p(x)$应按$i$升序排列，以形如(p_i, i)的对列表表示，其中$p_i$是非零系数。每个非零系数$p_i$需表示为最简分数$a/b$（$b > 0$），若$b=1$则仅打印$a$（省略$b$）。若$p(x) = 0$，则打印仅包含(0,0)的行。列表中的对用单个空格分隔。
• $q(x)$的打印格式与$p(x)$相同。
• 不同测试用例之间插入一个空行。

输入数据 1

2 2 0 0 1 1  
4 2 1 2 3 4 5 -2  
1 1 2 3  
1 4 -5 0 -2 1 -2  
0 0  

输出数据 1

(0,0)  
(1,1)  

(-4/33,0) (-1/11,1) (-2/33,2) (-1/33,3)  
(-4/33,0) (5/33,1)  

(2/3,0)  
(1/3,0)  

(25/6,0)  
(-5/6,0) (1/3,2) (-1/6,3)  

来源

2000年北美中东部地区赛