UOJ Logo Universal Online Judge

UOJ

#269. 【清华集训2016】如何优雅地求和

附件下载 统计

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

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

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

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

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

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

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

$$Q(f,n,x) = \sum_{k = 0}^{n}f(k){n\choose k}x^k(1 - x) ^{n - k}$$

现在给定函数 $f$ 和 $n,x$,求 $Q(f,n,x)\bmod 998244353$。

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

你能帮帮他吗?

出于某种原因,函数 $f$ 由点值形式给出,即给定 $a_0,a_1,\cdots,a_m$ 共 $m+1$ 个数,$f(x)=a_x$。可以证明该函数唯一。

输入格式

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

第二行共 $m+1$ 个整数,表示 $a_0,a_1,\cdots,a_m$。

输出格式

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

样例一

input

4 1 332748118
0 1

output

332748119

explanation

注意到 $332748118 \equiv \frac{1}{3} \pmod{ 998244353 }$, $332748119 \equiv \frac{4}{3} \pmod{ 998244353 }$, $f(x)=x$, 题目中所求的表达式为:

$$\sum_{k=0}^4 k{4\choose k}\left(\frac{1}{3}\right)^k\left(\frac{2}{3}\right)^{4-k}=\frac{4}{3}$$

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

样例二

input

4 3 12
0 1 8 27

output

46704

explanation

经计算可得 $f(x)=x^3$

样例三

见样例数据下载。

限制与约定

对于所有的测试点,保证 $1 \le n \le 10^{9},\ 1 \le m \le 2 \times 10^{4},\ 0\le a_i,x< 998,244,353$。

测试点$n \le$$m \le$特殊限制
1$10^{2}$$10^{2}$$n=m$
2$10^{3}$$10^{3}$
3$10^{4}$$10^{2}$无约束
4$10^{5}$
5$10^{6}$
6$10^{9}$$= 1$
7$= 2$$f(x)=x^2$
8$f(x)=x^2-x$
9$= 3$无约束
10,11$10$
12,13,14$10^{2}$
15$10^{3}$
16$2,000$
17$4,000$
18$8,000$
19$12,000$
20$2 \times 10^{4}$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载