Poly

多项式相关

这里是多项式相关的算法笔记。

默认文中的形如 \([l,r)\) 的区间为其与整数集的交集。

设原多项式为 \(F(x) = \sum_{i \in [0,n)} a_i x ^ i\)，其中 \(n = 2 ^ k, k \in \mathbb Z ^ +\)。

我们要求 \(\forall i \in [0,n),\hat a_i = F(t_i)\)，其中 \(t\) 是一个长度为 \(n\) 且两两互不相同的序列。

显然 \(F\) 可以被一组 \(\hat a,t\) 唯一确定，即点值表示法。

本文中使用 \(\cap\) 表示按位与，用 \(\cup\) 表示按位或

给定长度为 \(2^n\) 的数列 \(A,B\)，求 \(C_i = \sum_{j \cup k = i} A_j \times B_k\)

显然有 \(O(4^n)\) 的暴力

这一部分可以参考 FMT 中的 Zeta 变换，即定义 \(\hat A_i\) 为序列 \(A\) 中 \(i\) 的子集和

考虑分治

对于长度为 \(2^n\) 的待求解的 \(\hat A\)，我们把它分成独立的两部分，即 \([0,2^{n-1})\) 和 \([2^{n-1},2^n)\) 两个区间分别求解

然后考虑这两个区间之间的贡献，发现只有 \([0,2^{n-1})\) 对 \([2^{n-1},2^n)\) 有贡献，于是对于 \(i \in [0,2^{n-1})\)，将 \(\hat A_{i}\) 加到 \(\hat A_{i+2^{n-1}}\) 中即可

时间复杂度 \(O(n 2^n)\)

小 Tips：在计算机语言中 \(\cap\) = & / and， \(\cup\) = | / or

定义长度为 \(2^n\) 的序列的 and 卷积 \(A = B * C\) 为 \(A_i=\sum_{j \cap k = i}{B_j \times C_k}\)

考虑快速计算