P6620 [NOI Qualifier Joint Exam 2020 Paper A] Binomial Coefficient Problem

1s 512M

As everyone knows, student Xiaocong is good at calculations, especially at computing binomial coefficients. Now Xiaocong wants you to compute $$\left(\sum_{k=0}^{n}f(k)\times x^k\times \binom{n}{k}\right)\bmod p$$ where $n$, $x$, and $p$ are given integers, and $f(k)$ is a given degree $m$ polynomial $f(k) = a_0 + a_1k + a_2k^2 + \cdots + a_mk^m$. $\binom{n}{k}$ is the binomial coefficient, defined as $\binom{n}{k} = \frac{n!}{k!(n-k)!}$.

The first line contains four non-negative integers $n$, $x$, $p$, $m$. The second line contains $m + 1$ integers, representing $a_0$, $a_1$, $\cdots$, $a_m$.

Output one integer in a single line, which is the answer.

#### Sample 1 Explanation $f(0) = 0，f(1) = 1，f(2) = 4，f(3) = 9，f(4) = 16，f(5) = 25$. $x = 1$, so $x^k$ is always $1$, and this factor in each term of the product can be ignored. $\binom 5 0 = 1, \binom 5 1 = 5, \binom 5 2 = 10, \binom 5 3 = 10, \binom 5 4 = 5, \binom 5 5 = 1$. #### Sample 3 See the attached files `problem3.in` and `problem3.ans`. #### Constraints and Hints For all testdata: $1\le n, x, p \le 10^9, 0\le a_i\le 10^9, 0\le m \le \min(n,1000)$. The specific limits for each test point are shown in the table below: | Test Point ID | $n\le $ | $m\le $ | Other Special Limits | | :----------: | :-----: | :-----: | :------------------: | | $1\sim 3$ | $1000$ | $1000$ | | | $4\sim 6$ | $10^5$ | $0$ | $p$ is prime. | | $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$ | | Translated by ChatGPT 5