[省选联考 2020 A 卷] 组合数问题
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
#3300. 「联合省选 2020 A」组合数问题
标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |
题目描述
众所周知，小葱同学擅长计算，尤其擅长计算组合数。小葱现在希望你计算
$$\left(\sum_{k=0}^n f(k) \times x^k \times \binom n k\right) \bmod p$$的值。其中 为给定的整数， 为给定的一个 次多项式 。
为组合数，其值为 。
输入格式
第一行四个非负整数 。 第二行 个整数，分别代表 。
输出格式
仅一行一个整数表示答案。
样例 1
输入
5 1 10007 2
0 0 1
输出
240
，，，，，。
，故 恒为 ，乘积中的该项可以忽略。
$\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(k) \times \binom 5 k = 0\times 1 + 1\times 5 + 4\times 10 + 9\times 10 + 16\times 5 + 25\times 1 = 240$$样例 2
输入
996 233 998244353 5
5 4 13 16 20 15
输出
869469289
见附加文件中 problem3.in 与 problem3.ans。
数据范围与提示
对于所有测试数据：$1\le n, x, p \le 10^9, 0\le a_i\le 10^9, 0\le m \le \min(n,1000)$。
每个测试点的具体限制见下表：
| 测试点编号 | 其他特殊限制 | ||
|---|---|---|---|
| 是质数 | |||