【统一省选2020】组合数问题 - 题目

众所周知，小葱同学擅长计算，尤其擅长计算组合数。小葱现在希望你计算

$(\sum_{k = 0}^{n} f (k) \times x^{k} \times (\binom{n}{k})) mod p$

的值。其中 $n, x, p$ 为给定的整数， $f (k)$ 为给定的一个 $m$ 次多项式 $f (k) = a_{0} + a_{1} k + a_{2} k^{2} + \dots + a_{m} k^{m}$ 。

$(\binom{n}{k})$ 为组合数，其值为 $(\binom{n}{k}) = \frac{n!}{k! (n - k)!}$ 。

第一行四个非负整数 $n, x, p, m$ 。

第二行 $m + 1$ 个整数，分别代表 $a_{0}, a_{1}, \dots, a_{m}$ 。

一行一个整数表示答案。

5 1 10007 2
0 0 1

$f (0) = 0 ， f (1) = 1 ， f (2) = 4 ， f (3) = 9 ， f (4) = 16 ， f (5) = 25$ 。

$x = 1$ ，故 $x^{k}$ 恒为 $1$ ，乘积中的该项可以忽略。

$(\binom{5}{0}) = 1, (\binom{5}{1}) = 5, (\binom{5}{2}) = 10, (\binom{5}{3}) = 10, (\binom{5}{4}) = 5, (\binom{5}{5}) = 1$ 。

最终答案为：

$\sum_{k = 0}^{5} f (5) \times (\binom{5}{k}) = 0 \times 1 + 1 \times 5 + 4 \times 10 + 9 \times 10 + 16 \times 5 + 25 \times 1 = 240$

996 233 998244353 5
5 4 13 16 20 15

869469289

见附加文件中 ex_problem3.in 与 ex_problem3.ans。

对于所有测试数据： $1 \leq n, x, p \leq 10^{9}, 0 \leq a_{i} \leq 10^{9}, 0 \leq m \leq min (n, 1000)$ 。

每个测试点的具体限制见下表：

测试点编号	$n \leq$	$m \leq$	其他特殊限制
$1 \sim 3$	$1000$	$1000$	无
$4 \sim 6$	$10^{5}$	$0$	$p$ 是质数
$7 \sim 8$	$10^{9}$	$0$	无
$9 \sim 12$		$5$	无
$13 \sim 16$		$1000$	$x = 1$
$17 \sim 20$		$1000$	无

时间限制: $1 s$

空间限制: $512 MB$

Universal Online Judge