P6620组合数问题如何转化为？

P6620 [省选联考 2020 A 卷] 组合数问题 大意 求 \[\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_1k + a_2k^2 + \cdots + a_mk^m\)。\(\binom{n}{k}\) 为组合数，其值为 \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)。 思路 好题！ 我们先考虑这个式子的暴力处理方式，我们发现是外层枚举 \(k\)，内层枚举 \(f(k)\) 的 \(k\)，这样是 \(\mathcal{O}(nm)\) 的，但是我们发现 \(1 \le n \le 10 ^ 9\)，但是我们的 \(m\) 是 \(1 \le m \le 10 ^ 3\) 的，我们首先考虑的是把复杂度中的 \(n\) 化为用 \(m\) 的复杂度能解决的事情。 我们发现原始的式子中，只有 \(f(k)\) 是需要我们额外处理的，所以我们先看这个东西，我们考虑化简，这个时候需要用到 \(k\) 次下降幂的东西，众所周知 $x ^ k = x \times x \times \ldots $，那么我们的 \(x ^ {\underline{k}} = x(x - 1) \ldots (x - k + 1)\)，为什么我们需要知道这个东西呢？因为我们发现 \(f(k)\) 中的 \(k ^ j\) 无法很好的运算，我们考虑幂的转化，即利用第二类斯特林数将 \(x ^ k \to x ^ {\underline{k}}\)，如何做呢？我们有这样的恒等式：\(k ^ i = \sum_{j = 0}^{i} {i \brace j} k ^ {\underline{j}}\)。 那这个时候就有人要问了，主播主播什么是第二类斯特林数？我们考虑组合意义，是这样的： \({i \brace j}\) 表示将 \(i\) 个互不相同的球放到 \(j\) 个相同的盒子里（每个盒子都不为空）的方案数。那递推式就是：\({i \brace j} = {i - 1 \brace j - 1} + j \times {i - 1 \brace j}\)，那这个式子我们可以用组合的方式去理解一下，就是左边的 \({i - 1 \brace j - 1}\) 就是开一个新的盒子，而右边的 \(j \times {i - 1 \brace j}\) 就是用旧的盒子。 好，回到正题，我们考虑将原始的 \(f(k)\) 优化代换一下，用 \(k ^ {\underline{j}}\) 替代 \(k ^ j\)，这样的话前面会产生一个新的系数，我们将这个系数记为 \(b_j\)，那么 \(b_j = \sum_{i = 1}^{m} a_i \times {i \brace j}\)。