P5349 幂

题目大意

即求

$$ S = \sum_{n=0}^\infty f(n)r^n $$

分析

换序

$$ S = \sum_{n = 0}^{\infty} \left( \sum_{i = 0}^m f_i n^i \right) r^n = \sum_{i = 0}^m f_i \sum_{n = 0}^{\infty} n^i r^n $$

令

$$ S_i = \sum_{n = 0}^{\infty} n^i r^n $$

套路的逐项相减，主动的凑二项式

$$ (1 - r) S_i = 1 + \sum_{n = 1}^{\infty} n^i r^n - \sum_{n = 1}^{\infty} (n - 1)^i r^n = 1 + \sum_{n = 0}^{\infty} r^{n + 1} \sum_{j = 0}^{i - 1} \binom{k}{j} n^j $$

交换求和顺序

$$ (1 - r) S_i = 1 + \sum_{j = 0}^{i - 1} \binom{k}{j} \sum_{n = 0}^{\infty}r^{n + 1} n^j = 1 + \sum_{j = 0}^{i - 1} \binom{k}{j} r S_j $$

再凑成完整的二项式卷积

$$ \frac{S_i - 1}{r} = \sum_{j = 0}^i \binom{k}{j} S_j $$

我们设 $\{ S_i \}$ 的 EGF 为 $g(x)$，可以得到方程

$$ \frac{g(x) - 1}{r} = {\rm e}^x g(x) $$

解得

$$ g(x) = \frac{1}{1 - r {\rm e}^x} $$

因此最终多项式逆即可，EGF 和 OGF 的转化就是点乘阶乘。

int main() {
	int m = rr() + 1, r = rr();
	int lim = get_lim(m, m);
	w = pre_w(lim);
	Inv = pre_inv(lim);
	fac = pre_fac(lim);
	ifac = pre_ifac(fac);

	poly_t gg(lim, 1); // 初始化为 1

	gg = ntt_ogf2egf(gg, lim);

	for (int i = 0; i < lim; i++)
		gg[i] = Mint(0) - gg[i] * r;
	gg[0] += 1;

	gg = ntt_inv(gg, lim);

	gg = ntt_egf2ogf(gg, lim);

	Mint ans = 0;

	for (int i = 0; i < m; i++) {
		int fi = rr();
		ans += gg[i] * fi;
	}

	printf("%d", ans.v);

	return 0;
}