Skip to content

1382: 进行一个多项式的算

题目

题目描述

科学计算作业中,布罗需要计算若干个最高次项高达 $ 10^{21} $的多项式的值,正苦恼时,路过的铁哥发现了这些多项式的规律,即这些多项式可以表示为

$P(x,y_0,y_1,...,y_n)=a_0(1+y_0+y_0^2+...+y_0^{K_0})+a_1x(1+y_1+y_1^2+...+y_1^{K_1})+...+a_nx^n(1+y_n+y_n^2+...+y_n^{K_n})$.

其中$\forall K_i ,0\le K_i\le 10^{16},n \le 10^6,|a_i| \le 1e9$.

当然计算结果过于庞大,布罗只需要$P(x,y_0,y_1,...,y_n) mod p$的值,其中p是一个质数。

经过铁哥的点拨,布罗知道了该怎么计算这个多项式。但由于布罗的编译器还没动工,所以将这个问题交给你来解决了。

输入格式

第一行 n,x,p

接下来n+1行为 $a_i,y_i,K_i$

数字间用空格隔开。

输出格式

输出一个整数,表示最后的计算结果。

样例输入

0 1 5 1 2 8

样例输出

1

数据范围

对于前20%的数据,$n \le 10, K_i \le 100$

对于前40%的数据,$n \le 10, K_i \le 10^5$

对于前60%的数据,$n\le 10^6,K_i=0$

对于100%的数据,$n\le 10^4, 0 \le x,y_i,a_i \le 10^8, 0 \le K \le 10^{16}, 0 < p \le 10^{10}$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!