多项式结构的定义

我们引入多项式的结构 $(U,\otimes)$，其中 $S$ 为幂级数中形式幂取到的集合，而 $\otimes$ 代表运算。当 $A,B\in(S,\otimes)$ 时，我们定义 $[x^i]A$ 为取多项式 $A$ 的系数，当可以直接定义 $A$ 时则写作 $\mathcal A$，则 $A,B$ 的卷积满足
$$[x^k](AB)=\sum_{i,j\in U}[i\otimes j=k]\mathcal A_i\mathcal B_j$$
OI 中常见的 $U$ 是形如 $\mathbb Z(2^n)$ 或者 $\{1\le x\le n|x\in\Z\}$。第一部分的算法，将围绕着前一种可能；而第二部分的算法，则围绕着第二部分的算法。

第一部分 - $U=\mathbb Z(2^n)$

快速数论变换

这里直接通过原根到达快速数论变换。

牛顿迭代法

对数、指数、幂、长除法

拉格朗日插值

例题

第二部分 - $U=\{1\le x\le n|x\in\Z\}$

快速莫比乌斯变变换、快速沃尔什变换

例题

AtCoder ABC212H - Nim Counting

题目。给定 $n,S\subseteq[1,V]$，求满足如下条件的集合 $A$ 的数目：

• $A\subseteq S$。
• $\bigoplus_{k\in A}k\neq 0$。

解：我们设原来的多项式 $F\in(\mathbb Z,\oplus)$ 满足 $\mathcal F_i=[i\in S]$，那么最终的解应当是 $\sum_{j=1}^{2^V}[x^j]\sum_k F^k$。不幸，它有些慢。不过，我们知道 FWT 的两个性质：
$$([x^k]\mathrm{fwt}\{A\})^n=[x^k]\mathrm{fwt}\{A^n\}$$
$$[x^k]\mathrm{fwt}\{A+B\}=[x^k]\mathrm{fwt}\{A\}+[x^k]\mathrm{fwt}\{B\}$$
这两个性质可以允许我们做到下面的操作。即
$$\sum_{k=1}^n F^k=\sum_{k=1}^nF^k=\sum_{k=1}^n\mathrm{ifwt}\{(\mathrm{fwt}\{F\})^k\}=\mathrm{ifwt}\left\{\sum_{k=1}^n(\mathrm{fwt}\{F\})^k\right\}$$
展开，得到
$$=\mathrm{ifwt}\left\{\sum_{k=1}^n\sum_{j}([x^j]\mathrm{fwt}\{F\})^kx^j\right\}$$
我们把 $[x^k]\mathrm{fwt}\{F\}$ 记作 $\mathcal G_k$，那么按照等比数列求和公式，我们有
$$=\mathrm{ifwt}\left\{\sum_{k}\frac{\mathcal G_k^{n+1}-\mathcal G_k}{\mathcal G_k-1}x^k\right\}$$
这个可以直接求。其实这篇题解是错的，你可以试试找到错误原因。提示：就在前一行。