专栏文章

一个题

aanalysis
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minzdjmm
此快照首次捕获于
2025/12/02 10:50
3 个月前
此快照最后确认于
2025/12/02 10:50
3 个月前
查看原文
之前有人给的一道题，今天想起来了。
fi={1    i=0∑j=2i+1(−1)jj!fi−j+1    i≥1f_i=\begin{cases}1\ \ \ \ i=0\\\sum_{j=2}^{i+1}\frac{(-1)^j}{j!}f_{i-j+1} \ \ \ \ i\ge1\end{cases}
f(x)=∑i=0nfi×n!(n−i+1)!xn−i+1f(x)=\sum_{i=0}^n \frac{f_i\times n!}{(n-i+1)!}x^{n-i+1}。
给定 n,qn,q，多组询问 f(x)f(x)。
0≤n≤10180\le n\le10^{18}，0≤x，q≤3×1050\le x，q\le3\times10^5。
先求出数列。
手动补齐递推式剩下的两项得到 fi+1=∑j=0i+1fj(−1)i+1−j(i+1−j)!f_{i+1}=\sum_{j=0}^{i+1}f_j \frac{(-1)^{i+1-j}}{(i+1-j)!}。
另外根据变换前的形式得到 f1=2−1f_1=2^{-1}。
设 {fn}n≥0\{f_n\}_{n \geq 0} 对应的 OGF 为 F(t)F(t)，则：
F−t=Fe−t⇔F=t1−e−tF - t = Fe^{-t} \Leftrightarrow F=\frac{t}{1-e^{-t}}
现在求解答案。
先把 n!n! 提出来，再补齐卷积：
f(x)=n!(∑i=0n+1fixn+1−i(n+1−i)!−fn+1)f(x)=n![tn+1]F(ext−1)f(x)=n![tn]et(ext−1)et−1f(x)=n![tn]∑i=1xetif(x)=∑i=1xinf(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\\
O(X)O(X) 预处理，O(1)O(1) 查询。
至于那个 n,x≤1018,q=1n,x \leq 10^{18},q=1 的 bouns，我不好评。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...