U497631 拉格朗日插值法の判断
题目背景
这道题其实是有一天我看到这个数学题而想出来的，为此专门学了一下拉格朗日插值法
>题目：给定序列1,2,4,8,16,32,114514,1919810
>
>求其通项式
[hhh](https://www.luogu.com.cn/article/4itmf9e4)
没什么，只是觉得 ~~可以拿来装b~~ 比较有意思
---
基本公式：
$$L_n(x)=\sum^{n-1}_{i=0}y_ip_i(x)\\\\
p_i(x)=\prod^{n-1}_{j=0,j\not=i}\dfrac{x-x_j}{x_i-x_j}$$
这里对 $0\sim n-1$ 的 $n$ 个点进行插值
其中 $\sum$ 为循环求和， $\prod$ 为循环求积
你可以理解为： $\sum_{i=1}^ni$ 等价于下面的代码（其中 $ans$ 为答案）：
```cpp
for(int i=1;i
题目描述
今天并不需要你来计算拉格朗日插值法，因为 Bright12077 已经算好了结果
但是 Bright12077 是一个粗心的人，翻一翻数学学探诊第 14 章就能发现许多解得非常精妙的题：
1. $2x\cdot4x^2=2x^3$
2. $(-5ax)\cdot(3x^2y)^2=-15ax^5y^2$
3. $2x\div2x=0$
4. $(2x+1)(2x-1)=2x^2-1$
……
---
好了现在别乐了，由于 Bright12077 被数学作业恶心到了，于是他决定恶心一下你
他已经对 $n$ 个数进行了拉格朗日插值法的计算，其中第 $i$ 个数是 $a_i$，但是粗心的他经常会写错很多东西，因此他希望你能写一个程序，判断他公式的正确性
对于一个标准的公式，应包括以下几点：
1. 公式的开头应为 ```f(x)=```
2. 公式的形式应为 ```(不含任何形式分数的整式)/一个整数```（简称第一种） 或 ```一个不含任何形式分数的整式```（简称第二种） ，若为前者 则不论 分子的这个整式 是多项式还是单项式 都应被括号 包裹起来
$\ \ \ \ $ 对于这一条，“任何形式的分数”的定义为 “含有小数点或分数线（即 ```/``` ）”，比如 ```5/2```、```0.333```、```114/0```、```514/1```、```191.0```都包括在内
3. 若公式形式为第一种，则最终结果的分母应为一个为大于 1 的正整数，且无法与分子再约分.具体约分相关内容可见“提示说明”
4. 对于整式
1. 整式应由一个或多个单项式组合而成，除第一项为正时可以省略加号，其余项与前一项连接时必有一个符号. 如 ```x^54x^4``` 就是一个显然的缺少符号连接的式子. 不过 Bright12077 不会特别蠢，每一个单项式中只会包含一个 $x$，因此你可以用这一特性判断本条
2. $x$ 前的系数为 1 时需省略系数，为 -1 时需仅为 ```-``` ，为 0 时应省略该项，但当整个整式仅有 ```0``` 这一项时不应省略
3. 若该整式为多项式，则应按照 $x$ 的降幂排序输出，若其次数为 1 则省略次数，若为 0 则省略 $x$ 连同后面的指数，否则按照 ```x^次数``` 的格式
4. 整个整式中不应有任何括号（除非在第一种形式中将整个整式包裹起来的括号）
5. 将 $x=1\sim n$ 代入 $f(x)$ 进行计算，若函数的返回值依次为 $a_{1\sim n}$ 则整个公式没有问题，否则公式就有大问题
但是，Bright12077 肥肠自信，如果你判断他的程序有问题需要你给出对应的问题所在
**关于问题的返回应如下：**
1. 若公式不是以 ```f(x)=``` 开头，则输出 ```Prefix Error```
2. 若公式不是 ```(不含任何形式分数的整式)/一个整数``` 或 ```一个不含任何形式分数的整式``` ，以及出现了不该有的字符或多余的括号，则需输出 ```Format Error```
3. 若公式为第一种，且分母含有奇怪的符号或分母为小于等于 1 的数，则输出 ```Denominator Error```
4. 如果其中有数值的绝对值超过了 $993244853$ ，则输出 ```0verflow Error```
5. 如果单项式之间缺少连接符，或者出现了相邻的符号，则输出 ```Connection Error```
6. 若公式为第一种，且分母可以与分子继续约分，则输出 ```GCD Error```
7. 若整式没有按照 $x$ 的降幂排序，则输出 ```5orting Error```
8. 若出现 ```0x```、```1x```、```-1x```、```x^0```、```x^1```、```-0```、```+0``` 或由以上几种方式组合而成的如 ```0x^5```、```-1x^1``` 等，则输出 ```Monomial Error```
9. 可证明的，一个拉格朗日插值法得出的式子其最高次项的次数不会高于 $n-1$ （其中 $n$ 表示插值的元素数），因此当最高项次数大于 $n-1$ 时，输出 ```Times Error```。同样的，若出现 ```整数^整数```的情况，则同样按照此方式处理
10. 当对于一个 $x\ (x\in[1,n],x\in\mathbb{N})$ 但 $f(x)\not=a_x$ 时，输出 ```Wrong Answer on f(%d)``` ，其中 ```%d``` 应为第一次 $f(x)$ 出错时 $x$ 的值（允许 Bright2077 的公式答案误差 $10^{-3}$ ，因为 Bright12077 并不信任计算机的精度）
11. 当整个式子没有任何问题的时候，输出 ```Bright12077 is very handsome```
---
**一些注意事项**
1. 对于一个式子同时满足多种错误信息时，你应输出更靠前的一项
2. 当出现 ```(整式)``` 的形式时，应当做 ```Format Error``` 处理
3. 若数字含有前导零，可按照 ```+0``` 或 ```-0``` 处理（好一个断章取义）
（未完，如有其它可以提醒他人的地方可以来提议）
输入格式
第一行一个字符串，即 Bright12077 的公式
第二行一个数，$n$
第三行 $n$ 个数，表示 $a$ 数组
输出格式
一行，即反馈
说明/提示
~~30组样例，累死了~~
**【数据范围】**
$n\le5,|a_i|\le500$
保证输入字符串 $s$ 的长度不为 0
设公式中出现的绝对值最大的数值为 $T$
则保证有：
$\huge{-340282366920938463463374607431768211456\le\ T\ \le340282366920938463463374607431768211456\quad(2^{128})}$
本题共分为 ```subtask0``` 与 ```subtask1``` ，其中 ```subtask0``` 是标准数据，每点 1 分； ```subtask1``` 是征集的特殊数据，用于卡掉一些“看似 AC 但实际有漏洞”的程序，欢迎投稿
**【关于输入】**
很抱歉，由于作者是在 windows 环境下编辑的输入，导致在输入的末尾的换行可能会是 ```\r\n```
如果在本题中，你是使用 ```getline``` 进行的输入，请在输入的时做如下操作：
```cpp
string s;
getline(cin,s);
if(s[s.size()-1]=='\r')
s=s.substr(0,s.size()-1);//去除末尾元素（因为 '\r' 只会在末尾出现）
```
**【关于约分】**
~~如果你这都不会我很好奇你的十五章怎么学的~~
首先对于拉格朗日插值法，不难证明的，可以看作以下式子（其中 $a_i,b$ 为常数）：
$$f(x)=\dfrac{a_1n^{m_1}+a_2n^{m_2}+...+a_k+n^{m_k}}{b}$$
首先设 $g=\gcd(a_1,a_2,...，a_k)$，并将分子中的每一项提取出一个 $g$
再将 $g\leftarrow \gcd(g,b)$
可得最终结果
$$f_1(x)=\dfrac{a_1n^{m_1}+a_2n^{m_2}+...+a_k+n^{m_k}\div g}{b\div g}$$
不难证明，若最终的 $g\not=1$ ，则初始的 $f(x)$ 并不是最简分数