FZOJ4167 The Happy Prince and Other Tales 题解 _Other

学向勤中得，萤窗万卷书。这篇文章主要讲述FZOJ4167 The Happy Prince and Other Tales 题解相关的知识，希望能为你提供帮助。

The Happy Prince and Other Tales
给定长度为 (n+1) 的数列 (langle a_i angle_{i=0}^n)，请对于 (forall min[0,n]) 输出 (f_m(n)mod 998244353)，
[f_m(n)=sum_{i=0}^na_isum_{k=0}^ib^kinom{m}{k}inom{n-m}{i-k} ]
((nle 10^6,a_i,b< 998244353))

我们令
[a_i=sum_{j_1=0}^isum_{j_2=0}^{j_1}cdotssum_{j_p=0}^{j_{p-1}}inom{i}{j_1}inom{j_1}{j_2}cdotsinom{j_{p-1}}{j_p}c_{j_p} ]
则
[egin{aligned} f_m(n)=& sum_{i=0}^nsum_{j_1=0}^isum_{j_2=0}^{j_1}cdotssum_{j_p=0}^{j_{p-1}}inom{i}{j_1}inom{j_1}{j_2}cdotsinom{j_{p-1}}{j_p}c_{j_p}sum_{k=0}^ib^kinom{m}{k}inom{n-m}{i-k} =& sum_{j_p=0}^nc_{j_p}sum_{i=0}^nsum_{j_1=0}^isum_{j_2=0}^{j_1}cdotssum_{j_{p-1}=j_p}^{j_{p-2}}sum_{k=0}^ib^kinom{m}{k}inom{n-m}{i-k}inom{i}{j_1}inom{j_1}{j_2}cdotsinom{j_{p-1}}{j_p} \end{aligned} ]
存在
[egin{aligned} & sum_{i_1=0}^nsum_{i_2=0}^{i_1}cdotssum_{i_p=0}^{i_{p-1}}inom{n}{i_1}inom{i_1}{i_2}cdotsinom{i_{p-1}}{i_p}inom{i_p}{t}k^{i_1} =& sum_{i_1=0}^nsum_{i_2=0}^{i_1}cdotssum_{i_p=0}^{i_{p-1}}frac{n!}{(n-i_1)!(i_1-i_2)!cdots(i_{p-1}-i_p)!(i_p-t)!t!}k^{i_1} =& sum_{sum_{j=1}^pi_j=n-t}frac{n!}{t!prod_{j=1}^pi_j!}k^{n-i_1} \end{aligned} ]
发现这是一个多项式定理的形式，考虑生成函数，上式等于
[[x^t](kp+kx+1)^n ]
【FZOJ4167 The Happy Prince and Other Tales 题解】重新观察 (f_m(n))，可以进行如下化简
[egin{aligned} f_m(n)=& sum_{j_{p}=0}^nc_{j_p}sum_{k=0}[x^k](1+bp+bx)^m[x^{j_p-k}](1+p+x)^{n-m} =& sum_{j_{p}=0}^nc_{j_p}[x^{j_p}](1+bp+bx)^m(1+p+x)^{n-m} end{aligned} ]
我们令 (p=-1)，带入得
[f_m(n)=sum_{i=n-m}^nc_i[x^{i-(n-m)}](1-b+bx)^m=sum_{i=n-m}^nc_iinom{m}{i-(n-m)}b^{i-(n-m)}(1-b)^{n-i} ]
这是多项式卷积的形式，即
[frac{f_m(n)}{m!}=sum_{i}frac{b^{m-(n-i)}}{(m-(n-i))!}cdotfrac{(1-b)^{n-i}c_i}{(n-i)!} ]
我们现在来考虑如何求 (c)，根据反演，有
[c_i=sum_{j_1=0}^isum_{j_2=0}^{j_1}cdotssum_{j_p=0}^{j_{p-1}}inom{i}{j_1}inom{j_1}{j_2}cdotsinom{j_{p-1}}{j_p}(-1)^{i-j_1}(-1)^{j_1-j_2}cdots(-1)^{j_{p-1}-j_p}a_{j_p} ]
发现这个仍是多项式定理的形式，即
[c_i=sum_{j=0}^i[x^j](-p+sqrt[j]{a_j})^i=sum_{j=0}^iinom{i}{j}(-p)^{i-j}a_j=sum_{j=0}^iinom{i}{j}a_j ]
至此，共两次多项式卷积即可求出答案，时间复杂度 (O(nlog n))。

#include < iostream> using i64 = long long; namespace fio; namespace ply; using ply::MOD; using ply::fac; using ply::ifc; using ply::pow; const int N = 1000000 + 7; int n; i64 a[N], b, c[N]; int main() { fio::in(n), fio::in(b), ++n; for (int i = 0; i < n; ++i) fio::in(a[i]); static ply::polyT f, g, h; for (int i = 0; i < n; ++i) f[i] = ifc[i], g[i] = a[i] * ifc[i] % MOD; ply::mul(f, n, g, n, h); for (int i = 0; i < n; ++i) c[i] = h[i] * fac[i] % MOD; for (int i = 0; i < n; ++i) f[i] = pow(b, i) * ifc[i] % MOD, g[i] = pow(1 - b, i) * c[n - i - 1] % MOD * ifc[i] % MOD; ply::mul(f, n, g, n, h); for (int i = 0; i < n; ++i) fio::out((h[i] * fac[i] % MOD + MOD) % MOD), fio::put(‘ ‘); return 0; }