====== Contest Info ======

date: 2020.06.14 13:00-18:00

[[https://vjudge.net/contest/378303|practice link]]

====== 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)$ 多点求值求出所有常数项。