多项式多点求值.
给定 $a,b,c,d,n$ ,有一个函数
$$
f(x)=\frac{b}{c+\exp(ax+d)}
$$
记 $x_0$ 为 $ax+d=0$ 的唯一实根,即 $-\frac{d}{a}$ ,将 $f(x)$ 在 $x=x_0$ 处做泰勒展开,求 $(x-x_0)^n$ 这一项的系数.每组数据的 $n$ 是一样的,有 $q$ 次询问,每次询问给出 $a,b,c,d$ ,需要求出对应的答案,系数对 $998244353$ 取模.
$0\le n,q\le 3\times 10^5,a\neq 0$ .
一个靠谱做法
显然 $a,b,d$ 都没什么大用, $a,b$ 可以先忽略掉,最后乘上 $a^n\cdot b$ ,而 $d$ 只有平移的作用,可以直接忽略.
于是转化为求
$$
ans=[x^n]\frac{1}{c+\exp(x)} \\
$$
尝试把分母构造成 $1-q\cdot (\exp(x)-1)$ 的形式,对比系数不难发现 $q=-\frac 1{c+1}$ .
$$
\begin{aligned}
ans&=\frac{-1}{q}[x^n]\frac{1}{1-q\cdot (\exp(x)-1)} \\
&=\frac{-1}{q}[x^n] \sum_{k=0}^n q^k(\exp(x)-1)^k \\
\end{aligned}
$$
这里就能做了, $(\exp(x)-1)^k$ 再除个 $k!$ 就是第二类斯特林数一列的 EGF, 问题转化为求一行的第二类斯特林数.
如果继续往下推也不是很复杂,
$$
\begin{aligned}
ans&=\frac{-1}{q}[x^n] \sum_{k\ge 0}q^k\sum_{i=0}^k \binom k i\cdot \exp(ix)\cdot (-1)^{k-i}\\
&=\frac{-1}{q}[x^n] \sum_{i+j\le n}q^{i+j}\cdot\binom{i+j}{i}\cdot\exp(ix)\cdot(-1)^j\\
&=\frac{-1}{q}[x^n] \sum_{i+j\le n}q^{i+j}\cdot\binom{i+j}{i}\cdot \frac{i^n}{n!}\cdot(-1)^j
\end{aligned}
$$
EI : 处理倒数上有些奇怪东西的时候,就得强行加一再减一.
这里可以看出,强行凑出 $\exp(x)-1$ 的形式后,它的常数项是 $0$ ,枚举它的指数时就只用枚举到 $n$ 了.
不难发现这是个关于 $q$ 的 $n$ 次多项式,做一次卷积求出它,然后做多点求值即可.
特判掉 $c=-1$ 和 $n=0$ 的情况.
一个玄学做法
由于某种原因,答案为
$$
\frac{a^n\cdot b}{n!(c+1)^{n+1}}\cdot \sum_{i=0}^{n-1}(-1)^{n+i}\cdot E(n,i)\cdot c^i
$$
$E(n,k)$ 表示长度为 $n$ 的排列 $p$ ,恰有 $k$ 个位置满足 $p_i<p_{i+1}$ ,即恰有 $k+1$ 个极长单调下降的连续段方案数.
考虑容斥,钦定这 $k+1$ 段有 $i$ 个拼接的位置不合法,注意段可以为空,开头结尾也要算上,贡献是 $\binom{n+1}{i}$ .
然后把 $n$ 个数分到剩下的 $k+1-i$ 段中,段内会自动排成单调下降,且根据每一段的长度,分割的位置也会唯一确定.
$$
E(n,k)=\sum_{i=0}^k (-1)^i\binom{n+1}{i}(k+1-i)^n
$$
做一次卷积即可求出一行所有的 $E(n,k)$ ,得到 $\sum$ 这一坨关于 $c$ 的 $n-1$ 多项式,然后做多点求值即可.
特判掉 $c=-1$ 和 $n=0$ 的情况.
1 | //%std |