UOJ269 如何优雅地求和

神奇二项式反演 + 卷积。

题意：求 $\displaystyle \sum_{k = 0} ^ n f(k) \binom nk x ^ k (1 - x) ^ {n - k}$，其中 $f(x)$ 以给出 $[0, m]$ 的点值 $a_{0\dots, m}$ 形式给出。$n\leq 10 ^ 9, m\leq 2\times 10 ^ 4$。

这里给出一种神秘的做法：将 $f(x)$ 以下降幂的形式写出。即：

$$f(x) = \sum_{i = 0} ^ m b_i \dfrac{m ^ {\underline i}}{i!}$$

这个其实就是下降幂多项式。我们考虑如何求出 $b_i$，使用二项式反演（为了方便，还是使用广义组合数形式写出）：

$$b_n = \sum_{i = 0} ^ n (-1) ^ {n - i} \binom ni a_i$$

这个很容易化成卷积，这里不再展开。

然后考虑将这个带入可得：

$$\begin{aligned} ans =& \sum_{i = 0} ^ m b_i \sum_{k = 0} ^ n \binom nk\binom ki x ^ k (1 - x) ^ {n - k}\\ =& \sum_{i = 0} ^ m b_i \sum_{k = 0} ^ n \binom ni \binom{n - i}kx ^ k (1 - x) ^ {n - k}\\ =& \sum_{i = 0} ^ m b_i \binom ni x ^ i (x + 1 - x) ^ {n - k}\\ =& \sum_{i = 0} ^ m b_i \end{aligned}$$

后面的部分可以 $O(m)$ 算得。总时间复杂度 $O(m\log m)$。看到似乎有 $O(m)$ 做法？

int main()
{
	init();
	int n, m, x;
	std::cin >> n >> m >> x;
	std::vector<int> f(m + 1), g(m + 1);
	for (int i = 0; i <= m; ++ i) scanf("%d", &f[i]), f[i] = (LL) f[i] * infact[i] % Mod;
	for (int i = 0, op = 1; i <= m; ++ i, op = Mod - op)
		g[i] = (LL) op * infact[i] % Mod;
	f = f * g, f.resize(m + 1);
	int mul = 1, res = 0;
	for (int i = 0; i <= m; ++ i)
	{
		res = (res + (LL) f[i] * mul) % Mod;
		mul = (LL) mul * x % Mod * (n - i) % Mod;
	}
	std::cout << res << std::endl;
	return 0;
}