深刻认识到自己是彩笔的这一事实。

给定 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$ 是奇数

什么是 $NTT$

就是把把 $FFT$ 中所有的单位根换成了整数的单位根，也就是原根的 $n$ 次幂

通常用于求模意义下的多项式卷积

在上一篇文章里面我们介绍了 $FFT/IFFT$ 的基本原理和应用，今天我们来了解一下 $FFT$ 在字符串匹配中的神奇应用

引入问题

什么是多项式卷积

假设我们现在有多项式 $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}
$$

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