破防 P4091 [HEOI2016/TJOI2016] 求和

· · 个人记录

4. P4091 [HEOI2016/TJOI2016] 求和

给出 n，求：

\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{i}\begin{Bmatrix}i\\j\end{Bmatrix}2^j\cdot j!

我们对于数列 a=\langle0,1,1,1,\dots\rangle，有 EGF：

\hat F(x)=\sum\limits_{i\ge 1}\frac{x^i}{i!}=e^x-1

我们知道第二类斯特林数的一种表达方式：

\begin{Bmatrix}n\\k\end{Bmatrix}=\left[\frac{x^n}{n!}\right]\frac{\hat F(x)^k}{k!}=n!\cdot [x^n]\frac{\hat F(x)^k}{k!}

我们把 k! 乘过来，有：

k!\cdot \begin{Bmatrix}n\\k\end{Bmatrix}=n!\cdot [x^n]\hat F(x)^k

这说明了什吗？！

我们求一下 \hat F(x)^k，然后给各项系数乘一个阶乘，这之后的第 n 项系数就是 k!\cdot \begin{Bmatrix}n\\k\end{Bmatrix}。

这相当于我们枚举一个 k，然后计算 \hat F(x)^k 的各项系数。这么做铁定超时。但我们应该可以通过 \mathrm{e}^{\hat F(x)} 把 k 取遍 1\sim \infty 的系数求和，但怎么做呢？值得思考……

而且我们这个东西并不是题目要求的求和。

题干中要求的是一个 k!\cdot 2^k\cdot \begin{Bmatrix}n\\k\end{Bmatrix}，我们想办法凑一个 2^k 出来。

或许我们可以考虑构造函数 G：

G(x)=2^{k-x}

我们令 \hat F(x)^k 的每项系数乘以一个阶乘后的函数为 F_k'(x)。

然后求出 \hat F'_k(x)\cdot G(x)？复杂度炸炸炸。

我们考虑数列 b=\langle0,2,2^2,2^3\dots\rangle。

它有什么含义？饿哦不到啊？

踢完球回来接着看。有两条思路：

觉得还是有可能和生成函数关系大一点，但第二种思路很不会推啊

壹

我们令 A_j=j!\times 2^j，则对于每一个 i，都相当于求一行第二类斯特林数，和 A 的前 i 翻转后的卷积。

具体地，记 A'_{i-j}=j!\times 2^j

则对于每一个 i，计算下式：

\sum\limits_{j=0}^{i}\begin{Bmatrix}i\\j\end{Bmatrix}A'_{i-j}

这是卷积。可以 O(n\log n) 算。然后一行第二类斯特林数可以卷积 O(n\log n) 算，再加上枚举 i 的复杂度，总体就是 O(n^2\log n)。

比暴力还慢，但感觉可以走走。

肯定可以走了！我们这个东西是不是可以暴力卷？显然！

然后考虑一下卷积的实际意义。

贰

我们考虑答案可能为：

e^{\hat F(x)}=\sum\limits_{i=0}\frac{\hat F(x)^i}{i!}

的 0\sim n 项系数求和。

然后构造一个可能的 \hat F(x)？于是有：

\hat F(x)^i=i!\cdot \sum\limits_{j=0}^{i}\begin{Bmatrix}i\\j\end{Bmatrix}j!\cdot 2^j

想法构造一个 \hat F(x)。

感觉这条路很行不通。。。

急了急了急了急了

急急急

上面的都是脑瘫。我是脑瘫。

\begin{aligned}\\\\\\\\\\\\\\\\\\\end{aligned}