[清华集训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;
}
P6667