[清华集训2016] 如何优雅地求和

题目描述

有一个多项式函数 $f(x)$ ，最高次幂为 $x^m$ ，定义变换 $Q$ ：

$$Q(f,n,x)=∑_{k=0}^{n}f(k)\binom nkx^k(1−x)^{n−k} $$

现在给定函数 $f$ 和 $n,x$ ，求 $Q(f,n,x)\bmod998244353$ 。

题解

copy大佬的。

和组合数问题长好像，看到组合数啥的就下降幂吧。令 $f(x)=\sum_{i=0}^mb_ix^{\underline{i}}$ 是下降幂多项式。

$$\begin{aligned}&\sum_{k=0}^n\sum_{i=0}^mb_ik^{\underline{i}}\dbinom{n}{k}x^k(1-x)^{n-k}\\=&\sum_{i=0}^mb_i\sum_{k=0}^n\dfrac{n!}{(k-i)!(n-k)!}x^k(1-x)^{n-k}\\=&\sum_{i=0}^mb_i\sum_{k=0}^n\dfrac{(n-i)^{\underline{k-i}}}{(k-i)!(n-k)!}n^{\underline{i}}x^k(1-x)^{n-k}\\=&\sum_{i=0}^mb_in^{\underline{i}}\sum_{k=0}^n\dbinom{n-i}{k-i}x^k(1-x)^{n-k}\\ =&\sum_{i=0}^mb_in^{\underline{i}}x^i\sum_{k=0}^{n-i}\dbinom{n-i}{k}x^{k}(1-x)^{n-i-k}\\ =&\sum_{i=0}^mb_in^{\underline{i}}x^i(x+1-x)^{n-i}\\ =&\sum_{i=0}^mb_in^{\underline{i}}x^i \end{aligned}$$

于是只用求它的系数就好了。

下降幂的 EGF：

$$\begin{aligned}\hat{U}_k(z)&=\sum_{n\ge k}\dfrac{n^{\underline{k}}z^n}{n!}\\&=\sum_{n\ge k}\dfrac{\frac{n!}{(n-k)!}z^n}{n!}\\&=\sum_{n\ge k}\dfrac{z^n}{(n-k)!}\\&=z^k\sum_{n\ge 0}\dfrac{z^n}{n!}=z^ke^z\end{aligned} $$

题目里给出的点值，考虑它的 EGF：

$$\begin{aligned}\sum_{n\ge 0}\dfrac{f(n)z^n}{n!}&=\sum_{n\ge 0}\dfrac{z^n}{n!}\sum_{j=0}^mf_jn^{\underline{j}}\\&=\sum_{j=0}^mf_j\sum_{n\ge 0}\dfrac{n^{\underline{j}}z^n}{n!}\\&=\sum_{j=0}^mf_j\hat{U}_j(z)\\&=e^z\sum_{j=0}f_jz^j\end{aligned} $$

也就是说，如果我们设点值的 $\rm EGF$ 为 $\hat{A}(z)$ ，系数的 $\rm OGF$ 为 $B(z)$ ，则它们满足：

$$\hat{A}(z)=e^zB(z) $$

即：

$$B(z)=e^{-z}\hat{A}(z) $$

代码

const int N = 1e5 + 5, pN = N << 3;
const int mod = 998244353, G = 3, invG = 332748118;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
#define clr(f, x) memset (f, 0, sizeof(int) * (x))
#define cpy(f, g, x) memcpy (f, g, sizeof(int) * (x))
	int add(int a, int b) { return a + b > mod? a + b - mod: a + b; }
	int dec(int a, int b) { return a - b < 0? a - b + mod: a - b; }
	int mul(int a, int b) { return 1ll * a * b % mod; }
	int qpow (int a, ll b) {
		int ans = 1;
		for (; b; b >>= 1, a = mul(a, a))
			if (b & 1) ans = mul(ans, a);
		return ans;
	}
	namespace poly {
		int tr[pN];

		void init (int n, int siz) {
			for (int i = 0; i < n; ++i)
				tr[i] = (tr[i >> 1] >> 1) | ((i & 1) << (siz - 1));
		}

		void NTT (int *f, int n, int op = 1) {
			for (int i = 0; i < n; ++i)
				if (i < tr[i]) swap(f[i], f[tr[i]]);
			for (int p = 1; p < n; p <<= 1) {
				int omega = qpow (op? G: invG, (mod - 1) / (p << 1));
				for (int j = 0; j < n; j += p << 1)
					for (int w = 1, k = 0; k < p; k++, w = mul(w, omega)) {
						int x = f[j | k], y = mul(w, f[j | k | p]);
						f[j | k] = add(x, y), f[j | k | p] = dec(x, y);
					}
			}
			if (!op) {
				int invn = qpow(n, mod - 2);
				for (int i = 0; i < n; i++) f[i] = mul(f[i], invn);
			}
		}
		void px(int *f, int *g, int lim) { for (int i = 0; i < lim; ++i) f[i] = mul(f[i], g[i]); }
		void times(int *f, int *g, int n, int m, int T) {
			int lim = 1, lsiz = 0; for (; lim < n + m; lim <<= 1, lsiz++);
			init(lim, lsiz);
			static int tmp[pN]; clr(f + n, lim - n), cpy (tmp, g, m), clr(tmp + m, lim - m);
			NTT(f, lim), NTT(tmp, lim); px(f, tmp, lim); NTT(f, lim, 0);
			clr (f + T, lim - 1), clr (tmp, lim);
		}
		void inv (int *f, int n) {
			static int g[pN], r[pN], tmp[pN];
			g[0] = qpow(f[0], mod - 2);
			int lim = 1, lsiz = 0;
			for (int len = 2; (len >> 1) <= n; len <<= 1) {
				lim = len, lsiz++; init(lim, lsiz);
				cpy(r, g, len >> 1); cpy(tmp, f, lim);
				NTT(tmp, lim); NTT(r, lim); px(r, tmp, lim); NTT(r, lim, 0); clr(r, len >> 1);
				cpy(tmp, g, len); 
				NTT(tmp, lim); NTT(r, lim); px(r, tmp, lim); NTT(r, lim, 0);
				for (int i = (len >> 1); i < len; ++i) g[i] = dec(mul(g[i], 2), r[i]);
			}
			cpy(f, g, n); clr(g, lim); clr(r, lim); clr(tmp, lim);
		}
		void div (int *f, int *g, int n, int m) {
			static int fR[pN], gR[pN];
			int L = n - m + 1;
			reverse(f, f + n); cpy(fR, f, L); reverse(f, f + n);
			reverse(g, g + m); cpy(gR, g, L); reverse(g, g + m);
			inv(gR, L); times(gR, fR, L, L, L); reverse(gR, gR + L);
			times(g, gR, n, n, n);
			for (int i = 0; i < m - 1; i++) g[i] = dec(f[i], g[i]);
			clr (g + m - 1, L);
			cpy(f, gR, L); clr(f + L, n - L);
		}
		void mof (int *f, int *g, int n, int m) {
			static int fR[pN], gR[pN];
			int L = n - m + 1;
			reverse(f, f + n); cpy(fR, f, L); reverse(f, f + n);
			reverse(g, g + m); cpy(gR, g, L); reverse(g, g + m);
			inv(gR, L); times(gR, fR, L, L, L); reverse(gR, gR + L);
			times(gR, g, L, m, m - 1);
			for (int i = 0; i < m - 1; i++) f[i] = dec(f[i], gR[i]);
			clr (f + m - 1, L); clr(gR, n); clr(fR, n);
		}
	}
	int n, m, x;
	int fac[N], inv[N], expn[N];
	void init(int n) {
		inv[1] = fac[0] = 1;
		for (int i = 1; i < n; i++) fac[i] = mul(fac[i - 1], i);
		inv[n - 1] = qpow (fac[n - 1], mod - 2);
		for (int i = n - 1; i; i--) inv[i - 1] = mul(inv[i], i);
		for (int i = 0; i < n; i++) expn[i] = i & 1? mod - inv[i]: inv[i];
	}
	int f[pN], g[pN], h[pN];
	int main () {
		n = Read(), m = Read() + 1, x = Read(); init(m);
		for (int i = 0; i < m; i++) f[i] = mul(Read(), inv[i]);
		poly::times(f, expn, m, m, m);
		int ans = 0, b = 1, p = 1;
		for (int i = 0; i < m; b = mul(b, n - i), p = mul(p, x), ++i) 
		   ans = add(ans, mul(f[i], mul(b, p)));
		printf ("%d\n", ans);
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}