多项式除法及求模

问题是这样的:给定一个 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

BZOJ-3509. [CodeChef] COUNTARI

给定一个长度为 n ~(1 \leq n \leq 10^5) 的数组 a_i~(0 \leq a_i \leq 3\cdot 10^4),问有多少对 (i, j, k) 满足 i < j < ka_i - a_j = a_j - a_k

也就是统计有多少对长度为 3 的等差子序列(题目连接 BZOJ-3509, CodeChef COUNTARI

例如 3 5 3 6 3 4 10 4 5 2,就有 (1, 3, 5), (1, 6, 9), (1, 8, 9), (3, 6, 9), (3, 8, 9), (5, 6, 9), (5, 8, 9), (4, 6, 10), (4, 8, 10) 一共 9 对

(more…)

Read More

从多项式乘法到快速傅里叶变换

概述

计算多项式的乘法,或者计算两个大整数的乘法是在计算机中很常见的运算,如果用普通的方法进行,复杂度将会是 \mathcal O(n^2) 的,还有一种分治乘法,可以做到 \mathcal O(n^{\log_23}) 时间计算(可以看这里)。下面从计算多项式的乘法出发,介绍快速傅里叶变换(Fast Fourier Transform, FFT)如何在 \mathcal O(n\log n) 的时间内计算出两个多项式的乘积。另外,存在只需要两次快速傅立叶变换就可以计算大整数乘法的方法,具体见实序列离散傅里叶变换的快速算法

准备知识

这里介绍一些后面可能会用到的知识(主要是关于多项式、卷积以及复数的),如果你已经知道觉得它太水了或者想用到的时候再看就跳过吧

多项式

简单来说,形如 a_0+a_1X+a_2X^2+\cdots+a_nX^n 的代数表达式叫做多项式,可以记作P(X)=a_0+a_1X+a_2X^2+\cdots+a_nX^na_0, a_1, \cdots, a_n 叫做多项式的系数X 是一个不定元,不表示任何值,不定元在多项式中最大项的次数称作多项式的次数

多项式的系数表示法

像刚刚我们提到的那些多项式,都是以系数形式表示的,也就是将 n 次多项式 A(x) 的系数 a_0, a_1, \cdots, a_n 看作 n+1 维向量 \vec a=(a_0,a_1,\cdots,a_n),其系数表示(coefficient representation)就是向量 \vec a

多项式的点值表示法

如果选取 n+1不同的数 x_0, x_1, \cdots, x_n 对多项式进行求值,得到 A(x_0), A(x_1), \cdots, A(x_n),那么就称 \{\left(x_i, A(x_i)\right) : 0 \leq i \leq n, i \in \mathbb Z\} 为多项式 A(x)点值表示(point-value representation)

多项式 A(x) 的点值表示不止一种,你只要选取不同的数就可以得到不同的点值表示,但是任何一种点值表示都能唯一确定一个多项式,为了从点值表示转换成系数表示,可以直接通过插值的方法

复数

后面提到的 i,除非作为 \sum 求和的变量,其余的都表示虚数单位 \sqrt{-1}

单位根

n 次单位根是指能够满足方程 z^n=1 的复数,这些复数一共有 n 个它们都分布在复平面的单位圆上,并且构成一个正 n 边形,它们把单位圆等分成 n 个部分

根据复数乘法相当于模长相乘,幅角相加就可以知道,n 次单位根的模长一定是 1,幅角的 n 倍是 0

这样,n 次单位根也就是

e^{\frac{2\pi ki}{n}}, k = 0, 1, 2, \cdots, n - 1

再根据欧拉公式

e^{\theta i}=\cos\theta + i\sin\theta

就可以知道 n 次单位根的算术表示

如果记 \omega_n=e^{\frac{2\pi i}{n}},那么 n 次单位根就是 \omega_n^0, \omega_n^1, \cdots, \omega_n^{n-1}

多项式的乘法

给定两个多项式 A(x), B(x)

 A(x) = \sum_{i=0}^na_ix^i = a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0 \\ B(x) = \sum_{i=0}^nb_ix^i = b_nx^n+b_{n-1}x^{n-1}+\cdots+b_1x+b_0

将这两个多项式相乘得到 C(x) = \sum_{i=0}^{2n}c_ix^i,在这里

c_i=\sum_{j+k=i,0\leq j,k\leq n}a_jb_kx^i

如果一个个去算 c_i 的话,要花费 \mathcal O(n^2) 的时间才可以完成,但是,这是在系数表示下计算的,如果转换成点值表示,知道了 A(x), B(x) 的点值表示后,由于只有 n+1 个点,就可以直接将其相乘,在 \mathcal O(n) 的时间内得到 C(x) 的点值表示

如果能够找到一种有效的方法帮助我们在多项式的点值表示和系数表示之间转换,我们就可以快速地计算多项式的乘法了,快速傅里叶变换就可以做到这一点

(more…)

Read More

BZOJ-3771. Triple

这题挺有意思的,来源是 SPOJ-TSUM,题意大概是,给出 n 个物品,第 i 个物品的价值为 x_i(0 < x_i \leq 4\cdot10^4),问在这 n 个物品中选出 1 个或 2 个或 3 个价值和是多少,对于每个价值求出方案个数,在这题中 (a, b)(b, a) 算作一种方案

例如有三个物品

x_1 x_2 x_3
1 2 3

选一个就可以得到 1, 2, 3 三种价值

选两个就可以得到 1+2, 1+3, 2+3 三种价值

选三个就可以得到 1+2+3 一种价值

所以最后答案就是

价值 1 2 3 4 5 6
方案数 1 1 2 1 1 1

(more…)

Read More