A5901 | 「联合省选 2020 A」组合数问题
时间限制1s
内存限制512MB
通过 / 提交0/0
题目描述
众所周知，小葱同学擅长计算，尤其擅长计算组合数。小葱现在希望你计算
$$ \left(\sum_{k=0}^n f(k) \times x^k \times \binom n k\right) \bmod p $$
的值。其中 $n, x, p$ 为给定的整数，$f(k)$ 为给定的一个 $m$ 次多项式 $f(k) = a_0 + a_1 k + a_2 k^2 + \cdots + a_m k^m$。
$\binom n k$ 为组合数，其值为 $\binom n k = \frac{n!}{k!(n-k)!}$。
$$ \left(\sum_{k=0}^n f(k) \times x^k \times \binom n k\right) \bmod p $$
的值。其中 $n, x, p$ 为给定的整数，$f(k)$ 为给定的一个 $m$ 次多项式 $f(k) = a_0 + a_1 k + a_2 k^2 + \cdots + 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$。
第二行 $m + 1$ 个整数，分别代表 $a_0, a_1, \dots, a_m$。
输出格式
仅一行一个整数表示答案。
输入输出样例
输入 #1
5 1 10007 2 0 0 1
输出 #1
240
输入 #2
996 233 998244353 5 5 4 13 16 20 15
输出 #2
869469289
对于所有测试数据：$1\le n, x, p \le 10^9, 0\le a_i\le 10^9, 0\le m \le \min(n,1000)$。
每个测试点的具体限制见下表：
| 测试点编号 | $n\le $ | $m\le $ | 其他特殊限制 |
| :---------: | :-----: | :-----: | :----------: |
| $1\sim 3$ | $1000$ | $1000$ | |
| $4\sim 6$ | $10^5$ | $0$ | $p$ 是质数 |
| $7\sim 8$ | $10^9$ | $0$ | |
| $9\sim 12$ | $10^9$ | $5$ | |
| $13\sim 16$ | $10^9$ | $1000$ | $x=1$ |
| $17\sim 20$ | $10^9$ | $1000$ | |
每个测试点的具体限制见下表：
| 测试点编号 | $n\le $ | $m\le $ | 其他特殊限制 |
| :---------: | :-----: | :-----: | :----------: |
| $1\sim 3$ | $1000$ | $1000$ | |
| $4\sim 6$ | $10^5$ | $0$ | $p$ 是质数 |
| $7\sim 8$ | $10^9$ | $0$ | |
| $9\sim 12$ | $10^9$ | $5$ | |
| $13\sim 16$ | $10^9$ | $1000$ | $x=1$ |
| $17\sim 20$ | $10^9$ | $1000$ | |
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？