Description

\(n,q\le 3\times10^5\),要你对 \(q\) 组询问 \((a,b,c,d)\) 回答

\[ \frac{d}{c+e^{ax+b}} \]

\(x_0=-b/a\) 处的泰勒展开 \((x-x_0)^n\) 项系数。

Analysis

作代换 \(t=ax+b\),不难发现答案就是 \([t^n]a^n\cdot\frac{d}{c+e^t}\) ,那么 \(a,b,d\) 都处理完了。

考虑求 \([x^n]\frac{1}{c+e^x}\)

Method 1

这是我的方法,比较直来直去,但也用到了不少有意思的东西。

先是套路推式子,对于分式我们肯定想着用广义二项式定理或者本质相同的东西去弄,也就是必须要弄成 \(\frac{1}{1-P(x)}\) 的形式。我习惯几乎无副作用的乘除法,所以就是这么推的:

\[ \text{Origin}=\frac{1}{c}\cdot\frac{1}{1-(-c^{-1}e^{ax+b})} \] \[ \frac{1}{1-(-c^{-1}e^{x})}=\sum_i^\infty (-1/c)^{i}e^{ix} \]

\(n\) 次项系数,就是 \(e^{ix}\to\frac{i^n}{n!}\),就变成关于 \(-\frac1c\) 的一个无穷级数求和

\[ \frac{1}{n!}\sum_i^\infty(-1/c)^i\cdot i^n \]

这个东西先看成多项式乘等比数列的求和。我们有个结论就是对于 \(n\) 次多项式 \(f(x)\) \(\sum f(x)q^x=g(x)q^x-g(0)\) ,其中 \(g(x)\) 也是 \(n\) 次多项式。只要取 \(q=-1/c,f(x)=x^n\) 就是我们要求的。而再取 \(x\to\infty\)\(q^x\) 也莫得了,我们求的其实就是 \(-g(0)\)

对于 \(g\) ,我们根据上式差分可以得到递推式:

\[ g(i+1)=(-c)(g(i)+i^n) \]

然后展开递归式,一直到能用 \(kg(0)+b\) 的形式表示为止,考虑每一项的贡献,可以容易地将它写成和式

\[ g(i)=(-c)^ig(0)+\sum_{1\le j\le i}(-c)^{i-j+1}j^n \]

另外我们把它看作 \(n\) 次多项式 \(g(x)\) ,它的 \(n+1\) 次差分必为 \(0\) ,也就是说

\[ \sum_{i=0}^{k+1}{(-1)}^{k+1-i}\binom{k+1}{i}g(i)=0 \]

这样总共集齐了 \(n+1\) 个方程,或者反过来说,我们把所有 \(g(i)\) 都写成了 \(kg(0)+b\) 的形式,代入最后一个方程就能解出我们的答案 \(g(0)\)

那么接下来进行代入:

\[ k_{\text{Left}}=\sum_{i=0}^{n+1}(-1)^{n+1-i}\binom{n+1}{i}(-c)^i=(-c-1)^{n+1} \]

非常优美!刚好凑出一个二项式定理,让我们信心大增。

接下来的式子呢?

\[ b_{\text{Right}}=\sum_{i=0}^{n+1}(-1)^{n+1-i}\binom{n+1}{i}\sum_{j=1}^i(i-j+1)^n(-c)^j \]

不难发现它可以视作项为 \((-c)^j\) 的多项式,等下我们就可以用多项式多点求值了,一大心头之患解决了。那么接下来就是求系数,求系数的话肯定要更换求和顺序,把 \(j\) 先枚举。

\[ \sum_{j=1}^{n+1}(-c)^j\sum_{i=j}^{n+1}(-1)^{n+1-i}\binom{n+1}{i}(i-j+1)^p \]

我们要求的就是第二个和号起的那截了,注意到它是个卷积的形式,NTT 出来就好了。

然后 \(b/k\) 就是我们的初步答案(答案是 \(-g(0)\),别忘了那个负号),后续还要乘上 \(a^n,\frac{1}{n!}\) 等等因子,别漏了,不然直接自闭。

复杂度的话,对于 \(k\),可以每个 \(c\)\(\mathcal O(\lg n)\) 求;\(b\) 必须整体地跑多点求值,但依然可以 \(\mathcal O(q\lg^2n)\) 求。总复杂度 \(\mathcal O(q\lg^2n)\)

Method 2

事情其实远没有那样困难

——只要你能查书(大雾)

首先我们知道上面所说的 多项式乘等比数列的求和 其实就是多重对数函数的特殊情形……

那篇文章其实是我年少无知时写的,不过那都已经过去了。

文章末尾,当时留了几个悬念的式子,自己都不太懂有什么用的式子,谁能想到今天它就派上用场了呢?

上主菜!

\[{\rm Li}\_{-n}(z)={1\over (1-z)^{n+1}}\sum\_{k=0}^{n-1}\left\langle{n\atop k}\right\rangle z^{n-k}\]

嘛,这个式子其实是我直接查维基百科的“多重对数”词条得到的。

其中 \(\displaystyle\left\langle {n\atop k}\right\rangle\),大家都读过《具体数学》,应该知道指的就是欧拉数。

你知道欧拉数咋求吗?其实就是对幂函数做二项式反演。

\[ \left\langle {n\atop k}\right\rangle=\sum_{i=0}^k (-1)^i\binom{n+1}{i}(k+1-i)^n \]

喂,你小子,我怎么看你这么眼熟?(草)

嗯,这个就是其中一个 \(b\) ,一样地做卷积就能做了。

Method 3

链接

jklover 桑的做法,他给的第二种“玄学做法”就是我以前的式子,我已经给出解释了,看到这篇题解的时候我还挺惊讶的,原来早有人抢先我一步做出了这种做法,虽然暂时不知道是谁想出来的。

而第一种是所谓的“靠谱”做法,用加减而不是乘除凑结构还是蛮值得学习的,确实有时候能构造出更好的结构,但是后面观察出就是斯特林数的生成函数什么的还是算了吧?無理無理!

Method 4

如果在一开始接着使用乘除,到无穷级数求和那一步的时候把 \(k^n\) 采用第二类斯特林数展开为下降幂,好像也能做,细节我没有推了。

Implementation

你不会想看的。(qi shi shi hai mei xie)