#2076. 如何优雅地求和
如何优雅地求和
如何优雅地求和
题目描述
标题: 如何优雅地求和 - Problem - QOJ.ac
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
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 1 332748118
0 1
332748119
样例 2
4 3 12
0 1 8 27
46704