当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6414:带劲的多项式

题目描述
光羽的高等代数挂科了,度度熊非常难受,于是带劲出了一道高代水题来安慰他!

定义模域$P$下的$d$次多项式$A(x)=\sum_{i=0}^{d} a_i x^i$,其中$a_i$是整数且$0 \le a_i < P$。其中$P=998244353$。

定义模域$P$下$n$次多项式$A(x)$和$m$次多项式$B(x)$的乘法为:
$A(x)B(x)= \sum_{s=0}^{n+m} (\sum_{i+j=s} a_i b_j) \% P \times x^s$
其中$\% P$表示对质数P取模。

给出模域P下多项式$f(x)= \sum_{i=0}^{n} a_i x^i$,$(0 \le a_i < P)$。

这个多项式很**带劲**,它**保证**可以表示成这样:
$f(x)= (x - \lambda_1)^{l_1}(x - \lambda_2)^{l_2}..(x - \lambda_m)^{l_m}.$
(因为数据就是这么造的。)

其中$0 \le \lambda_i < P$且$\lambda_i$两两不同,同时满足$l_1 < l_2 < .. < l_m$且$\sum_{i=1}^{m} l_i = n$。注意此处乘法为之前定义的模域下乘法。

给出n和n+1个数$a_0,a_1,..,a_n$,求出$\lambda_1,\lambda_2,...,\lambda_m$和$l_1,l_2,...,l_m$。

**由唯一分解定理知答案唯一。**
输入解释
第一行一个数,表示数据组数$T$。

每组数据第一行仅包含一个数$n$;第二行$n+1$个数,分别为$a_0,a_1,...,a_n$。

数据组数T=100,$1 \le n \le 2000$。
其中90%的数据满足$1 \le n \le 200$。
输出解释
每组数据输出$m+1$行,第一行仅包含一个数表示$m$,接下来m行,每行两个数$\lambda_i,l_i$,**要求按照$l_i$升序输出。**
输入样例
3
5
998241761 3024 998243057 264 998244327 1
5
0 0 0 64 998244337 1
5
998233985 8208 998241761 408 998244321 1
输出样例
2
2 1
6 4
2
8 2
0 3
2
8 1
6 4
来自杭电HDUOJ的附加信息
Recommend chendu

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6414

最后修改于 2020-10-25T23:31:07+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000/1000MS(Java/Others) 65536/65536K(Java/Others)