https://wiki.cvbbacm.com/ 2026-04-30T10:52:37+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2021-02-15T11:27:27+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:2021%E5%B9%B4%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:lgwza:%E5%BF%AB%E9%80%9F%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2_fft&rev=1613359647&do=diff 快速傅里叶变换(FFT) 原理 OI Wiki-快速傅里叶变换 例题 例 1 题意 P3803 【模板】多项式乘法（FFT） 给定一个 $n$ 次多项式 $F(x)$，和一个 $m$ 次多项式 $G(x)$。求出 $F(x)$ 和 $G(x)$ 的卷积。 题解 通过 DFT 和 IDFT 两个过程，实现多项式由系数表示法 -> 点值表示法 -> 系数表示法。利用单位根的性质实现奇偶分治过程，时间复杂度 $O(n\log n)$$a,b$$a\times b$$1\le a,b\le 10^{1000000}$$n$$k$$k=\overline{a_{n-1}a_{n-2}\cdots a_2a_1a_0}=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}(x=10)$$O(n\log n)$$n$$n$$q_1,q_2,\cdots,q_n$$$ F_j=\sum_{i=1}^{j-1}\frac{q_i\times q_j}{(i-j)^2}-\sum_{i=j+1}^{n}\frac{q_i\times q_j}{(i-j)^2}\\ … text/html 2021-02-15T22:01:24+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:2021%E5%B9%B4%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95:lgwza:%E5%BF%AB%E9%80%9F%E6%95%B0%E8%AE%BA%E5%8F%98%E6%8D%A2_ntt&rev=1613397684&do=diff 快速数论变换(NTT) 原理 OI Wiki-快速数论变换(NTT) 例题 例 1 题意 P3803 【模板】多项式乘法（FFT） 给定一个 $n$ 次多项式 $F(x)$，和一个 $m$ 次多项式 $G(x)$。求出 $F(x)$ 和 $G(x)$ 的卷积。$1\le n,m\le 10^6$ 题解 找到模数 $p$，使得 $p=qn+1,(n=2^k)$，对于模 $p$ 的原根 $g$，$\displaystyle g_n\equiv g^q\equiv g^{\frac{p-1}{n}}$，可以看作 FFT 中 $n$ 次单位根 $\omega_n$ 的等价，因为它们都是各自所在群的生成元。所以 NTT 的代码只需把 FFT 中的 $\omega_n$$g^{\frac{p-1}{n}}$$a,b$$a\times b$$1\le a,b\le 10^{1000000}$$2$$F(x),G(x)$$F(x)*G(x)$$p$$p$$p=a\cdot 2^k+1$$1\le n,m\le 10^5,0\le a_i,b_i\le 10^9,2\le p\le 1…