Powerful Number
[题解] [Mivik 的萌新赛 & Chino 的比赛 2020] Ame 和 Gura 的奇妙探险

[题解] [Mivik 的萌新赛 & Chino 的比赛 2020] Ame 和 Gura 的奇妙探险

给定 MT19937 的 10 个参数 $N$、$M$、$A$、$U$、$S$、$B$、$T$、$C$、$L$ 和 $F$,以及 $N$ 个引擎刚被初始化后生成的随机数,要求推断出初始化 MT19937 使用的种子。

$10\le M<N\le 2\times 10^5$,$0\le A,B,C<2^{32}$,$1\le U,S,T,L\le 31$,$1\le F<2^{32}$,保证 $F$ 是奇数

阅读更多
FFT | 3 | 数论变换NTT基础
FFT | 2 | FFT在字符串匹配中的应用
FFT | 1 | 基础傅立叶变换知识

FFT | 1 | 基础傅立叶变换知识

引入问题

什么是多项式卷积

假设我们现在有多项式 $f(x)$ 和 $g(x)$ ,它可以被表示为

$$
f(x)=\sum_{i=0}^{n-1} a_i\cdot x^i\\
g(x)=\sum_{i=0}^{m-1} b_i\cdot x^i
$$

其中 $a$ 和 $b$ 为系数数组, $n$ 和 $m$ 分别为两个多项式的长度

那么它们的卷积为

$$
f(x)\bigotimes g(x)=\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} a_i\cdot b_j\cdot x^{i+j}
$$

也可以表示成

$$
c_k=\sum_{i=0}^ka_i\cdot b_{k-i}
$$

其实就是简单的两个多项式相乘

阅读更多