#PQJ983x4552. QOJ 983_4552

    ID: 3084 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTT 2016

QOJ 983_4552

标题: 如何优雅地求和 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

π+e 在高中上数学课时经常睡觉,然而每次考试都能 AK,这让他的同桌叶子很是膜拜。

某天,老师在课上讲二项分布的题目:

(2010天津,18改)
某射手每次射击击中目标的概率p=1/3, 且各次射击的结果相互独立, 互不影响。
记4次中击中的次数为X, 求X的数学期望与期望的方差。
(答案:4/3,8/9)

老师说:“这个,二项分布的期望就是 np,方差就是 np(1−p),不信你们自己课后回去算。”

π+e 一听有附加题,马上打起了精神,三下五除二用了他的黑科技“母函数求导”就轻而易举的解决了这个问题。顺便帮叶子也给科普了一下。

2016年暑假的某天,π+e 突然想起了这件事。他想了想,把原来的问题加强了一下,变成下面这个样子:

有一个多项式函数 f(x),最高次幂为 xm,定义变换 Q:

Q(f,n,x)=∑k=0nf(k)(nk)xk(1−x)n−k

现在给定函数 f 和 n,x,求 Q(f,n,x)mod998244353。

然而,众所周知,高考考完是会掉很多智商的。π+e 发现自己已经忘记掉怎么用的黑科技了;他打电话给叶子,叶子也说不记得了。

你能帮帮他吗?

出于某种原因,函数 f 由点值形式给出,即给定 a0,a1,⋯,am 共 m+1 个数,f(x)=ax。可以证明该函数唯一。

输入格式

第一行三个整数 n,m,x,意义如前所述。

第二行共 m+1 个整数,表示 a0,a1,⋯,am。

输出格式

输出一行一个数表示答案,请对 998,244,353 取模。

样例一

input

4 1 332748118
0 1

output

332748119

explanation

注意到 332748118≡13(mod998244353), 332748119≡43(mod998244353), f(x)=x, 题目中所求的表达式为:

∑k=04k(4k)(13)k(23)4−k=43

此即为题目开头二项分布例题计算期望的表达式。

样例二

input

4 3 12
0 1 8 27

output

46704

explanation

经计算可得 f(x)=x3

样例三

见下发文件。

限制与约定

对于所有的测试点,保证 1≤n≤109, 1≤m≤2×104, 0≤ai,x<998,244,353。

测试点n≤m≤特殊限制1102102n=m21031033104102无约束410551066109=17=2f(x)=x28f(x)=x2−x9=3无约束10,111012,13,1410215103162,000174,000188,0001912,000202×104