一个题

· · 个人记录

之前有人给的一道题，今天想起来了。

f_i=\begin{cases}1\ \ \ \ i=0\\\sum_{j=2}^{i+1}\frac{(-1)^j}{j!}f_{i-j+1} \ \ \ \ i\ge1\end{cases} 给定 $n,q$，多组询问 $f(x)$。 $0\le n\le10^{18}$，$0\le x，q\le3\times10^5$。

先求出数列。

手动补齐递推式剩下的两项得到 f_{i+1}=\sum_{j=0}^{i+1}f_j \frac{(-1)^{i+1-j}}{(i+1-j)!}。

另外根据变换前的形式得到 f_1=2^{-1}。

设 \{f_n\}_{n \geq 0} 对应的 OGF 为 F(t)，则：

F - t = Fe^{-t} \Leftrightarrow F=\frac{t}{1-e^{-t}}

现在求解答案。

先把 n! 提出来，再补齐卷积：

f(x)=n!(\sum_{i=0}^{n+1} f_i\frac{x^{n+1-i}}{(n+1-i)!} - f_{n+1})\\ f(x)=n![t^{n+1}]F(e^{xt}-1)\\ f(x)=n![t^n]\frac{e^t(e^{xt}-1)}{e^t-1}\\ f(x)=n![t^n]\sum_{i=1}^{x}e^{ti}\\ f(x)=\sum_{i=1}^{x}i^n\\ 至于那个 $n,x \leq 10^{18},q=1$ 的 bouns，我不好评。