牛顿迭代法在多项式运算的应用

总算是快把 FFT 和生成函数的各种东西补了好多,膜拜策爷的论文和 Picks 的博客 QAQ

这篇文章大概就是说如何用牛顿迭代法来解满足 G(F(z)) \equiv 0 \pmod {z^n}F(z)

然后这东西可以比较方便地计算 \sqrt{A(z)}e^{A(z)},也就是多项式开根、求指数对数之类鬼畜的东西,在生成函数计数中十分有用

顺便一提,这里说的“多项式”实际上你可以直接理解为生成函数或者形式幂级数

(more…)

Read More

多项式的多点求值与快速插值

多项式的多点求值(multi-point evaluation)是给出一个多项式 A(x),和 n 个点 x_0, x_1, \cdots, x_{n-1},要求求出 A(x_0), A(x_1), \cdots, A(x_{n-1})

相反的,多项式的插值(interpolation)是给出 n+1 个点 (x_0, y_0), (x_1, y_1), \cdots, (x_n, y_n),求出一个 n 次多项式,使得这些点都在这个多项式上

这两个问题实际上是在多项式的点值表示(point-value representation)和系数表示(coefficient representation)之间转换的方法,在快速傅里叶变换中由于带入值的特殊性质,可以在 \mathcal O(n\log n) 的之间内将两种东西互相转换,但是,如果是任意给定点要求求值或者插值,就没有比较好的性质可以利用,但是仍然有比较快速的方法来计算它们

(more…)

Read More

多项式除法及求模

问题是这样的:给定一个 n 次多项式 A(x) 和一个 m(m \leq n) 次多项式 B(x),要求求出两个多项式 D(x), R(x),满足

 \begin{equation} \label{div0} A(x) = D(x)B(x) + R(x) \end{equation}

并且 deg D \leq degA - degB = n - mdegR < m

在解决这个问题之前你需要掌握多项式求逆,利用快速傅里叶变换可以在 \mathcal O(n\log n) 的复杂度内求出这个问题的解

多项式除法在很多问题中都有应用,例如多项式的扩展欧几里得算法、线性递推的优化等等

(more…)

Read More

BZOJ-3557. [Ctsc2014]随机数

这是 CTSC2014 一道陈老师的可怕题目!

露露、花花和萱萱最近对计算机中的随机数产生了兴趣。为大家所熟知的是,由计算机生成的随机数序列并非真正的随机数,而是由一定法则生成的伪随机数。

某一天,露露了解了一种生成随机数的方法,称为 Mersenne twister。给定初始参数 m \in \mathbb Z^+x \in \mathbb Z \cap [0, 2^m) 和初值 M_0 \in \mathbb Z \cap [0, 2^m),它通过下列递推式构造伪随机数列 {M_n}

 \begin{equation*} M_n = \left \{ \begin{aligned} &2M_{n-1}& ~2M_{n-1} < 2^m \\ (2M_{n-1} &-2^m) \oplus x & ~2M_{n-1} \geq 2^m \\ \end{aligned} \right. \end{equation*}

其中 \oplus 是二进制异或运算(C/C++ 中的 ^ 运算)。而参数 x 的选取若使得该数列在长度趋于无穷时,近似等概率地在 \mathbb Z \cap (0, 2^m) 中取值,就称 x 是好的。例如,在 m > 1x=0 就显然不是好的。

在露露向伙伴介绍了 Mersenne twister 之后,花花想用一些经典的随机性测试来检验它的随机性强度。为此,花花使用计算机计算了一些 M_k

但细心的萱萱注意到,花花在某次使用二进制输入 k 时,在末尾多输入了 l0。她正想告诉花花这个疏忽,然而花花已经计算并记录了错误的 M_k 值而没有记录 k 的值。虽然这其实不是什么致命的问题,但是在萱萱告诉花花她的这个疏漏时,作为完美主义者的花花还是恳求萱萱帮她修正 M_k 的值。萱萱便把这个任务交给了他的 AI ——你!

【输入格式】

输入文件 random.in 的第一行包含一个正整数 m,第二行为二进制表示的 x(共 m 个数,从低位到高位排列),第三行为二进制表示的 M_0(排列方式同 x),第四行包含一个整数 type

接下来分为两种可能的情况:

  1. type = 0(萱萱记下了花花的输入):则第五行包含一个整数,表示萱萱记下来的正确的 k 值。
  2. type = 1(萱萱未能记下花花的输入):则第五行为 l,第六行输入花花计算出错误的二进制表示的 M_k

【输出格式】

输出文件 random.out 仅一行,为一个 m 位的 01 串,表示你求得的正确的 M_k(同样要求从低位到高位排列)

【数据范围】

对于 type = 0 的部分,m, k \leq 10^6

对于 type = 1 的部分,m \leq 10^3, k \leq 10^{18}, l \leq 10x 是“好的”

每个数据点时限 20s,并且开启编译器优化

(more…)

Read More

扩展大步小步法解决离散对数问题

离散对数(Discrete Logarithm)问题是这样一个问题,它是要求解模方程

 a^x \equiv b \pmod m

这个问题是否存在多项式算法目前还是未知的,这篇文章先从 m 是质数开始介绍大步小步法(Baby Step Giant Step)来解决它,之后再将其应用到 m 是任意数的情况。这个算法可以在 \mathcal O(\sqrt m) 的时间内计算出最小的 x,或者说明不存在这样一个 x

题目链接:BZOJ-2480SPOJ-MODBZOJ-3239

(more…)

Read More

多项式求逆元

概述

多项式求逆元是多项式除法和多项式取模的必要过程,在竞赛中,有时候多项式求逆元的应用比多项式的除法还要多,用快速傅里叶变换以及倍增算法可以做到在 \mathcal O(n\log n) 的时间内求出一个多项式的逆元

基本概念

在介绍多项式的逆元之前,先说明一些概念:多项式的度、多项式的逆元、多项式的除法和取余

对于一个多项式 A(x),称其最高项的次数为这个多项式的(degree),记作 deg A

对于多项式 A(x), B(x),存在唯一Q(x), R(x) 满足 A(x) = Q(x)B(x) + R(x),其中 deg R < deg B,我们称 Q(x)B(x)A(x)R(x)B(x)A(x)余数,可以记作

 A(x) \equiv R(x) \pmod {B(x)}

(more…)

Read More