2020-2021:teams:intrepidsword:2019-hdu-multi-2

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:intrepidsword:2019-hdu-multi-2 [2020/06/14 21:47]
admin 创建
+++ 2020-2021:teams:intrepidsword:2019-hdu-multi-2 [2020/06/15 02:03] (当前版本)
admin fix link
@@ 行 6: / 行 6: @@
 ====== Solutions ======
+===== C. Coefficient =====
+**题目大意**：给定函数 $f(x)=\frac{b}{c+e^{ax+d}}(a\neq0)$，求其在 $x_{0}=-\frac{d}{a}$ 处泰勒展开第 $n$ 项 $(x-x_{0})^{n}$ 的系数。答案对 $998,244,353$ 取模。具体地说，给定一个 $n$，你需要回答 $q$ 组询问，每次给出不同的 $a,b,c,d$ 让你求答案。其中 $n,q\le5\times10^{4}$，$\sum n,\sum q\le3\times10^{5}$。
+**题解**：令 $t=ax+d$，那么 $f(t)=\frac{b}{c+e^{t}}$，故 $f(x)$ 的泰勒展开为 $f(x)=\sum_{i=0}^{+\infty}\frac{f^{(i)}(t)t^{i}}{i!}=\frac{a^{i}f^{(i)}(t)(x-x_{0})^{i}}{i!}$。所求系数即为 $a^{n}\frac{f^{(n)}(t)}{n!}$，也就是 $f(t)$ 的展开乘以 $a^{n}$。
+首先讨论几种特殊情况。
+  * 若 $n=0$，那么系数为 $\frac{b}{c+1}$。其中 $c=-1$ 时未定义。
+  * 否则，若 $c=-1$，那么 $f(t)=\frac{b}{-1+e^{t}}$，同样可以证明其各阶导数均未定义。
+  * 否则，若 $c=0$，那么 $f(t)=\frac{b}{e^{t}}$，$t^{n}$ 项系数为 $\frac{(-1)^{n}b}{n!}$。
+接下来讨论一般情况。
+$$
+\begin{aligned}
+f(t)&=\frac{b}{c+e^{t}}\\
+&=\frac{b}{c}\cdot\frac{1}{1-(-\frac{1}{c})e^{t}}\\
+&=\frac{b}{c}\sum_{i=0}^{+\infty}(-\frac{1}{c})^{i}e^{it}\\
+\end{aligned}
+$$
+其 $t^{n}$ 项系数为
+$$
+\begin{aligned}
+&\frac{b}{c}\sum_{i=0}^{+\infty}(-\frac{1}{c})^{i}\frac{i^{n}}{n!}\\
+=&\frac{b}{cn!}\sum_{i=0}^{+\infty}u^{i}i^{n}\\
+\end{aligned}
+$$
+这时便可用上[[.:zhongzihao:sequence_sum_v5|这里]]介绍的技巧求 $\sum_{i=0}^{+\infty}u^{i}i^{n}$。由于 $\lim\limits_{m\to\infty}u^{m}F(m)=0$，因而答案的极限为 $-F(0)$。令 $F(0)=x$，可得方程
+$$
+\begin{aligned}
+&\sum_{i=0}^{n+1}(-1)^{i}{n+1\choose i}\frac{f(i)+x}{u^{i}}\\
+=&(\frac{u-1}{u})^{n+1}x+\sum_{i=1}^{n+1}u^{i}i^{n}\sum_{j=i}^{n+1}\frac{(-1)^{j}{n+1\choose j}}{u^{j}}\\
+=&(\frac{u-1}{u})^{n+1}x+\sum_{i=1}^{n+1}i^{n}\sum_{j=i}^{n+1}\frac{(-1)^{j}{n+1\choose j}}{u^{j-i}}\\
+=&(\frac{u-1}{u})^{n+1}x+\sum_{i=0}^{n}\frac{1}{u^{i}}\sum_{j=i}^{n+1}(-1)^{j}{n+1\choose j}(j-i)^{n}\\
+=&0\\
+\end{aligned}
+$$
+注意到常数项是关于 $\frac{1}{u}$ 的多项式，那么可以在 $\mathcal{O}(n\log^{2}n)$ 多点求值求出所有常数项。

2020-2021/teams/intrepidsword/2019-hdu-multi-2.1592142476.txt.gz · 最后更改: 2020/06/14 21:47 由 admin