rushcheyo -《转置原理及其应用》学习整理.
由于本人学艺不精,这里仅从比较粗浅的角度记录一些应用.
多点求值新科技
给定一个 $n$ 次多项式 $F(x)$ 和 $m$ 个数 $a_i$ ,需要求出每个 $F(a_i)$ 的值.
定义减法卷积 ${\rm MULT}(F(x),G(x))=\sum_{i\ge0}(\sum_{j\ge 0}f_{i+j}g_j)x^i$ ,可以将一个多项式取反后再卷积来实现.
有 $F(a_i)=[x^0]{\rm MULT}(F(x),\frac{1}{1-a_ix})$ .
且
$$
{\rm MULT}(F(x),G(x)H(x))={\rm MULT}({\rm MULT}(F(x),G(x)),H(x))
$$
分治地来求每个 $F(a_i)$ .
$$
G(l,r,x):={\rm MULT}(F(x),\frac 1{\prod_{i=l}^r(1-a_ix)}) \bmod x^{r-l+1}\\
G(l,mid,x)={\rm MULT}(G(l,r,x),\prod_{i=mid+1}^r (1-a_ix))\bmod x^{mid-l+1}\\
G(mid+1,r,x)={\rm MULT}(G(l,r,x),\prod_{i=l}^{mid} (1-a_ix)) \bmod x^{r-mid}
$$
当递归到 $l=r$ 时,此时的 $G(l,r,x)$ 的常数项就是我们要求的点值了.
每个要用到的 $\prod_{i=l}^r (1-a_ix)$ 可以用分治 NTT 预处理出来,时间复杂度 $O(n\log^2 n)$ .
例题
真实无妄她们的人生之路
有 $n$ 件物品,第 $i$ 件物品有属性 $0\le p_i\le 1$ .
主人公等级初始为 $0$ ,使用第 $i$ 件物品会有 $p_i$ 的概率让等级加 $1$ , $1-p_i$ 的概率不变.
若最后等级为 $j$ ,则会产生 $a_j$ 的攻击力.
令 $f(i)$ 表示使用除 $i$ 外的 $n-1$ 个物品后,主人公产生的期望攻击力,需要求出 $f(1),f(2)\dots f(n)$ .
$1\le n\le 10^5$ ,答案对 998244353 取模.Source : Comet OJ #2 F
设位置 $i$ 的多项式 $F_i(x)=p_ix+1-p_i$ ,则 $i$ 的答案就是多项式 $\prod_{j\neq i} F_j(x)$ 与 $A(x)=\sum_i a_ix^i$ 的点积.
我们知道点积可以表示成减法卷积结果的常数项,即 $f(i)=[x^0] {\rm MULT}(A,\prod_{j\neq i} F_j)$ .
可以像做多点求值那样,由于减法卷积满足
$$
{\rm MULT}(F(x),G(x)H(x))={\rm MULT}({\rm MULT}(F(x),G(x)),H(x))
$$
在分治时,向左儿子传入当前乘积与右儿子 $\prod F$ 的减法卷积,向右儿子传入当前乘积与左儿子 $\prod F$ 的减法卷积.
时间复杂度 $O(n\log^2 n)$ .