NGC5457's Site

标签： 快速傅里叶变换

  • 再探 FFT – DIT 与 DIF，另种推导和优化

    本文将简单推导两种方式进行的离散傅里叶变换，用另种视角解释并优化算法。参考了 Seniorious yhx-12243 的 NTT 到底写了些什么（详细揭秘） 一文、OI Wiki 快速傅里叶变换 条目 和 rushcheyo 转置原理及其应用 讲稿。

    离散傅里叶变换

    我们计算数列 $\{a_n\}$ 的离散傅里叶变换
    $$
    \newcommand\DFT{\operatorname{DFT}}\DFT(a,n)_k=\sum_{j=0}^{n-1}a_j\mathrm{e}^{\frac{-2\pi\mathrm{i}}{n}kj}
    $$

    由卷积定理和循环卷积得到，我们对同样长为 $n$ 的数列 $\{b_n\}$ 作 $\DFT$，并令数列 $c_k=\DFT(a,n)_k\DFT(b,n)_k$，则有
    $$
    \newcommand\IDFT{\operatorname{IDFT}}\IDFT(c,n)_k=\sum_{j+q\equiv k\pmod n}a_jb_q
    $$

    于是我们可以利用该原理实现常规意义下的数列卷积：有长为 $n$ 的数列 $\{a_n\}$，长 $m$ 的数列 $\{b_m\}$，则将 $a,b$ 高位补 $0$，分别作 $n+m-1$ 位的 $\DFT$，点值相乘后 $\IDFT$ 即可得到 $c_k=\sum_{i+j\equiv k\pmod{n+m-1}}a_ib_j=\sum_{\substack{i+j=k\\0\leq i<n\\0\leq j<m}}a_ib_j$。

    为行文方便，下文采用 $\DFT(a,n)_k=\sum_{i=0}^{n-1}a_i\omega_n^{ik}$ 的定义，其中 $\omega_n=\exp(2\pi\mathrm{i}/n)$，即 $n$ 阶单位根。 （更多…）

  • 洛谷题库 P6031 Cards 加强版 – 题解与思路重现

    洛谷题库 P6031 Cards 加强版

    对于每一轮对局的 $m!$ 种排列，对于编号为 $a$ 的牌，恒有 $(m-1)!$ 种是以牌 $a$ 为首的。因此一轮可以归为 $m$ 种情况，首张为王牌的概率为 $\frac{1}{m}$。

    这是某场模拟考试给出的部分分：
    $$
    \begin{array}{cccc}
    \text{Subtask}&\text{Constraints}&\text{Points}&\text{Dependencies}\\ \hline
    1&n,m,k\leq 5&2&\\
    2&k=1&2&\\
    3&k\leq 5000&10&1,2\\
    4&m\leq 100&10&1\\
    5&n\leq k&5&\\
    6&k\leq 10^5&10&1,2,3\\
    7&k\leq 5\times 10^6&20&1,2,3,6\\
    8&&41&1\sim 7
    \end{array}
    $$ （更多…）

  • MOCK NOIP 20220920 B – 骰子 另解题解

    形式化题意

    给定 $A+B$ 个本质相同的随机变量，在 $\{1,2,\cdots,6\}$ 内等概率取值。若两个随机变量 $a \in A, b \in B, a=b$，则二者相消为 $0$。求在所有可能的消除完成后，存在 $a \leq t, a \in A, t \in \{1,2,\cdots,6\}$ 的概率。对 $10^9+7$ 取模。

    朴素DP

    令 $c_i$ 表示随机结果中数值为 $i$ 的 $A$ 内变量数；$d_i$ 同理。原题意可以转化为求出 $1-P(\text{不存在小于等于}t\text{的}a)$。由概率的定义，我们可以用能造成后者局面的方案总数除以 $6^{A+B}$ 既是结果。换句话说，原命题的否命题应当满足 $\forall i \in \{1,2,\cdots,t\}, c_i \leq d_i$。

    又因为这些随机变量本质相同，则由“可重集的排列数”得，若有确定的 $c_{1},c_2,\cdots,c_6, \sum_{i=1}^{6}c_i=A$，则掷出对应结果的方案数为
    $$\dbinom{A}{c_1}\dbinom{A-c_1}{c_2}\cdots\dbinom{A-\sum_{i=1}^{5}c_i}{c_6}=\dfrac{\color{blue}A!}{\prod_{i=1}^{6}c_i!}$$ （更多…）

  • 任意模数下快速数论变换的两种实现

    我们实现NTT时，总是在 整数模质数 $p=2^kq+1$ 域上进行的。原因很简单：为了在 $\mathbb{Z}/p\mathbb{Z}$ 上使用原根以套用复数域 $\mathbb{C}$ 上“单位根”的概念，其阶必然也应当是 $2^k$ 的倍数才行。这就为我们带来了很多不便。假如现在给定一质数 $p’$ 且不保证有 $p’=2^kq+1$，我们就需要另辟蹊径完成卷积。

    实现一：中国剩余定理

    中国剩余定理：若数 $n$ 的质因数分解为 $\sum_{i=1}^{k}p_i^{e_i}$，有整数模 $n$ 加法群（或者环，随便你怎么叫吧）

    $$\mathbb{Z}/n\mathbb{Z}\cong \mathbb{Z}/p_1^{e1}\mathbb{Z}\times \mathbb{Z}/p_2^{e2}\mathbb{Z}\times \cdots \times\mathbb{Z}/p_k^{ek}\mathbb{Z}$$

    或者通俗地讲，若 $m_1, m_2, \cdots, m_k$ 两两互质，则线性同余方程组
    $$\left\{\begin{aligned}
    x &\equiv x_1\pmod{m_1}\\
    x &\equiv x_2\pmod{m_2}\\
    &\quad \vdots\\
    x &\equiv x_k\pmod{m_k}\end{aligned}\right.$$
    在 $\bmod \prod_{i=1}^{k}m_i$ 意义下有唯一解。 （更多…）

  • FFT“三次转两次”优化

    众所周知，由于做快速傅里叶变换时，要先将两个多项式 $f(x),g(x)$ 分别DFT，点值相乘后再IDFT，其常数是巨大的。但如果其系数均为实数，我们就可以通过构造多项式的方式，充分利用复数虚部存储需要的信息。下文中默认有 $\operatorname{deg}(f(x))=\operatorname{deg}(g(x))=n=2^s$。记 $n$ 次单位根为 $\omega_{n}$。

    考虑构造两多项式 $p(x)=f(x)+\mathrm{i}g(x),q(x)=f(x)-\mathrm{i}g(x)$，则假若我们求出 $p(x)$ 的点值表示，就会有 $\overline{p(\omega_n^k)}=q(\omega_n^{-k\space\bmod n})$。 （更多…）

  • 分治FFT与循环卷积

    洛谷题库 P4721【模板】分治FFT

    给定数列 $g_{1\cdots n}$，求解满足如下形式的数列 $f$：$f_0=1,f_i=\sum_{j=0}^{i-1}f_jg_{i-j},\forall i \in \{1,2,\cdots,n\}$，对 $998244353$ 取模。

    这道题可以通过多项式求逆解决。我们在此不作讨论。

    考虑其转移形式，全部都是依赖于前序已求出项的、固定系数的线性转移。则可以考虑CDQ分治。如果你愿意，也可以叫作“分治FFT”。

    假设正处理区间 $[l, r]$；令 $\text{mid}=\lceil (l+r)/2\rceil$，我们已经计算好 $f_{l,\cdots,\text{mid}}$。现统一处理左半区间对右半的贡献。

    则令考虑的乘积项为 $f_i, i \in [l, \text{mid}]$，要向 $f_j, j \in (\text{mid}, r]$ 作贡献。有 $f_j \leftarrow g_{j-i}f_i$。故而对于 $i \in [l, \text{mid}]$，其将分别与 $g_{\text{mid}+1-l, \cdots, r-l}, g_{\text{mid}-l, \cdots, r-l-1}, \cdots, g_{1, \cdots, r-\text{mid}}$ 作卷积。其二者下标的和即为贡献对象。故而我们构造两个多项式 $F(x), G(x)$，有 $[x^i]F(x)=f_{i+l}, [x^j]G(x)=g_{j-1}$，将其二者作卷积，他们对 $f_j, j \in (\text{mid}, r]$ 的贡献即为 $[x^{j-l-1}]F(x)G(x)$。

    （更多…）