自动搬运

查看原文

来自洛谷，原作者为

	zhoukangyang ^w^/

搬运于2025-08-24 22:22:55，当前版本为作者最后更新于2021-01-24 14:27:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

更好的阅读体验

众所周知这题可以用斯特林数 $m^2$ 求，但是要快速插值斯特林数等一堆东西估计过不了。

令 $f(x) = \sum\limits_{i = 0}^{m} \binom{x}{i} s_i$。$\binom{x}{i}$ 是 $i$ 次多项式，因此存在这样的 $s$ 。

二项式反演：$f(x) = \sum\limits_{i = 0}^{x} \binom{x}{i} s_i \Leftrightarrow s_x = \sum\limits_{i = 0}^{x} \binom{x}{i} (-1)^{x - i} f(i)$

通过卷积可以快速得到 $s$ 数组。

通过这个我们可以快速得到一个点的点值。

（知道这个这题就不难了）

推式子：

$$\sum\limits_{k = 0}^{n} \sum\limits_{i = 0}^{m}s_i \binom{k}{i} \binom{n}{k} x^k (1 - x)^{n - k} $$$$\sum\limits_{k = 0}^{n} \sum\limits_{i = 0}^{m}s_i \binom{k}{i} \binom{n}{k} x^k (1 - x)^{n - k} $$$$\sum\limits_{k = 0}^{n} \sum\limits_{i = 0}^{m} s_i \binom{n}{i} \binom{n - i}{k - i} x^k (1 - x)^{n - k} $$$$\sum\limits_{i = 0}^{m} s_i \binom{n}{i} \sum\limits_{k = i}^{n} \binom{n - i}{k - i} x^k (1 - x)^{n - k} $$$$\sum\limits_{i = 0}^{m} s_i \binom{n}{i} \sum\limits_{k = 0}^{n - i} \binom{n - i}{k} x^{k + i} (1 - x)^{n - k - i} $$$$\sum\limits_{i = 0}^{m} s_i \binom{n}{i} x^i \sum\limits_{k = 0}^{n - i} \binom{n - i}{k} x^{k} (1 - x)^{n - i - k} $$$$\sum\limits_{i = 0}^{m} s_i \binom{n}{i} x^i (x + 1 - x)^{n - i} $$$$\sum\limits_{i = 0}^{m} s_i \binom{n}{i} x^i$$

这样就可以很方便地做了。

时间复杂度 $\Theta(m \log m)$

代码：

int fac[N], ifac[N];
void minit(int x) {
	fac[0] = 1;
	L(i, 1, x) fac[i] = (ll) fac[i - 1] * i % mod;
	ifac[x] = qpow(fac[x]);
	R(i, x, 1) ifac[i - 1] = (ll) ifac[i] * i % mod;
}
int fpow(int x) {
	return x % 2 == 0 ? 1 : mod - 1;
}
int n, m, x, f[N], g[N], s[N], ans;
int main() {
	n = read(), m = read(), x = read();
	minit(m), init(m << 1);
	L(i, 0, m) f[i] = (ll) ifac[i] * fpow(i) % mod;
	L(i, 0, m) g[i] = (ll) ifac[i] * read() % mod;
	Mul(f, g, s, m + 1, m + 1);
	L(i, 0, m) s[i] = (ll) s[i] * fac[i] % mod;
	int now = 1;
	L(i, 0, m) (ans += (ll) now * s[i] % mod * ifac[i] % mod) %= mod, now = (ll) now * x % mod * (n - i) % mod;
	cout << ans << endl;
	return 0;
}

祝大家学习愉快！