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

多项式的多点求值(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

BZOJ-3435. [Wc2014]紫荆花之恋

强强和萌萌是一对好朋友。有一天他们在外面闲逛,突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了,无数的花瓣以肉眼可见的速度从紫荆树上长了出来。

仔细看看的话,这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点,每个节点上有一个可爱的小精灵,新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物,每个小精灵 i 都有一个感受能力值 r_i,小精灵 i,j 成为朋友当且仅当在树上 ij 的距离 \text{dist}(i,j) \leq r_i+r_j,其中 \text{dist}(i,j) 表示在这个树上从 ij 的唯一路径上所有边的边权和。

强强和萌萌很好奇每次新长出一个叶子节点之后,这个树上总共有几对朋友。

我们假定这个树一开始为空,节点按照加入的顺序从 1 开始编号。由于强强非常好奇,你必须在他每次出现新结点后马上给出总共的朋友对数,不能拖延哦。

【输入格式】

第一行包含一个整数,表示测试点编号。

第二行包含一个正整数 n,表示总共要加入的节点数。

我们令加入节点前的总共朋友对数是 \text{last_ans},在一开始时它的值为 0

接下来 n 行中第 i 行有三个非负整数 ai,ci,ri,表示结点 i 的父节点的编号为 a_i \oplus (\text{last_ans} \bmod 10^9)(其中 \oplus 表示异或,\text{mod} 表示取余,数据保证这样操作后得到的结果介于 1i-1 之间),与父结点之间的边权为 c_i,节点 i 上小精灵的感受能力值为 r_i

注意 a_1=c_1=0,表示 1 号节点是根结点,对于 i>1,父节点的编号至少为 1

【输出格式】

包含 n 行,每行输出 1 个整数,表示加入第 i 个点之后,树上有几对朋友。

【数据范围】

n \leq 10^51 \leq c_i \leq 10^4a_i \leq 2\times 10^9r_i \leq 10^9,时限 12s

(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

BZOJ-2780. Sevenk Love Oimaster

题目给出 n 个字符串 s_1, s_2, \cdots, s_n,以及 m 个询问 q_1, q_2, \cdots, q_m,每个询问是一个字符串,要求计算 q_i 在多少个 s_1, s_2, \cdots, s_n 中出现过

例如 s_1=abcabc, s_2=ca, s_3=a,那么 abcs_1 中出现过,as_1, s_2, s_3 中出现过

数据范围:1 \leq n \leq 10^4, 1\leq q \leq 6\cdot 10^4, \sum_{i=0}^n |s_i| \leq 10^5, \sum_{i=0}^m |q_i| \leq 3.6 \cdot 10^5

题目连接:BZOJ-2780SPOJ-JZPGYZ

(more…)

Read More