快速傅里叶变换

形式化题意

给定 $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!}$$ （更多…）

众所周知，由于做快速傅里叶变换时，要先将两个多项式 $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})$。 （更多…）