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 对

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) 的点值表示

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

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

Read More

BZOJ-2001. [HNOI2010]City城市建设

题目给定一个有 n 个节点,m 条边的有向图,以及 q 个修改,每个修改更改一条边的权值,并且询问修改后的图的最小生成树,n\leq 20000, m \leq 50000, q \leq 50000

看了这篇题解才会做的QAQ

题目核心思想是分治以及缩小图的规模,有两个操作

Contraction:删除必须边

把待修改的边标记成 -\infty,然后跑一次最小生成树,显然这时候出现在生成树中非 -\infty 的边肯定会在之后的生成树中,所以我们记录下它们的权值和,然后在下一层分治的时候删除这些边

Reduction:删除无用边

把待修改的边标记成 \infty,然后跑一次最小生成树,没出现在生成树中的非 \infty 边在之后的生成树中肯定也不会出现(因为在当前图构造出的MST中,加入这条边会生成一个环,而且它是这个环中权值最大的边,然而在之后的图中,\infty 边只会变小,它还是权值最大的边,所以肯定不会出现在MST中),于是将它们删除,继续分治

然后每层分治过程中都进行 Contraction-Reduction 来缩小图的规模,在最后一层分治的时候使修改生效,做一遍MST就可以了(这时候图已经很小了所以会很快)

Read More

区间K小问题

Problem 1:无修改、无插入区间第K小问题

关于这题,可以直接用主席树(函数式线段树)来解决

假设现在有无限的内存和时间,可以对每个前缀构造一棵权值线段树,然后每次询问区间 [l, r] 就找出前缀 [0, l - 1] 和 [0, r] 的线段树,相减就可以得到所需要的权值线段树,然后在这上面根据子树大小跑就可以了

由于空间有限,最开始不初始化整棵树,而是动态的添加节点,并且在插入的时候只有经过的那一条链上的东西会被更改,所以对于一些没有修改的子树,直接用指针指向上一次的版本,因为每一次插入最多经过 \mathcal O(\log n) 个节点,这样总共空间不会超过 \mathcal O(n\log n),同样,时间复杂度也是每次 \mathcal O(\log n)

参考问题:BZOJ-2588: Spoj 10628. Count on a tree

Problem 2:带修改、无插入区间第K小问题

现在需要修改权值,如果暴力修改每棵线段树的话,最多会要修改 \mathcal O(n) 级别的东西,复杂度也会退化

这时候想想,我们需要的操作是修改一个区间的线段树和询问一个区间的线段树的信息,也就是区间修改和区间查询,很容易会想到树状数组!它能够把每个区间用 \mathcal O(\log n) 个区间来表示出来

所以只要在每个树状数组的节点建立可以权值线段树,表示这个区间的权值信息就可以完成所需要的操作了,时间和空间复杂度都是 \mathcal O(n\log^2 n)

参考问题:BZOJ-1901: Zju2112 Dynamic Rankings

Problem 3:带修改、带插入区间第K小问题

现在我们需要支持可以在某个位置插入一个值,比如原先的序列是 1 2 3,然后在第二个位置插入 4 的话,序列就会变成 1 4 2 3

因为树状数组不支持插入元素,但是类似 Problem 2 的思想,你或许会想到使用平衡树,它也在 \mathcal O(\log n) 的时间内支持区间修改、查询,而且还支持插入元素

也就是平衡树上的节点就表示整棵子树中信息的权值线段树,但是仔细想就会发现,平衡树基本都是需要旋转来维持平衡的,这样一转,对权值线段树修改的时间复杂度就会迅速增大!

替罪羊树(Scapegoat Tree)是一种很神奇的平衡树,它不需要旋转来保持平衡,而是有一个平衡因子 \alpha \in [0.5, 1] 每次插入如果发现某棵子树太不平衡,就把整棵子树暴力重构成完全二叉树

具体来说也就是如果某棵子树满足 \alpha \cdot size > \max (left\_size, right\_size),就认为是不平衡的,然后就重构它

\alpha = 0.5 的时候,这棵树就是完全二叉树,当 \alpha = 1 的时候就永远不会重构,很显然,\alpha 越小,询问的效率越高,\alpha 越大,插入的效率越高

可以证明,替罪羊树的查询效率是 \mathcal O(\log n),而插入均摊 \mathcal O(\log n)

这样,这个问题只需要用替罪羊树再套上权值线段树就可以解决了

但是有一个问题就是你需要动态分配内存,并且在重构的时候要及时释放无用内存。并且在写权值线段树的时候不要写成函数式线段树那样,否则内存会爆(我就不小心写成这样被坑了好久)

参考问题:BZOJ-3065: 带插入区间K小值

BZOJ-3695. 滑行

这是 2014 年福建省省队训练的时候首长出的一道题,然后听完讲评后整个人就不好了,题目大概是这样的

首长NOI惨跪,于是去念文化课了。现在,他面对一道物理题

现在有一个小滑块可以在地面上滑行,地面上被划分成不同的区域,使得小滑块在不同的区域内部有一个不同的速度上限

小滑块在(0,0)点,我们现在要推动小滑块到目标点(x,y)

地面上有 N 层区域,每层区域都是矩形,现在给你一个序列 \{H_i\} 表示每层区域的高度,覆盖的地面横坐标范围是 0~X,第i个区域的限速是 v_i

注: Y=\sum_{i=1}^nH_i,其它的地方小滑块不允许进入

现在我们要设计一个路线使得小滑块滑到目标点的用时最小

如果你知道两个物理学的定理(光的最速原理、折射定律),那么这题就可以很快解出来了

Read More

NOI2012. 迷失游乐园

放假了,小Z觉得呆在家里特别无聊,于是决定一个人去游乐园玩

进入游乐园后,小Z看了看游乐园的地图,发现可以将游乐园抽象成有n个景点、m条道路的无向连通图,且该图中至多有一个环(即 m 只可能等于 n 或者 n-1,并且环上节点个数不超过 25 个)。小Z现在所在的大门也正好是一个景点

小Z不知道什么好玩,于是他决定,从当前位置出发,每次随机去一个和当前景点有道路相连的景点,并且同一个景点不去两次(包括起始景点)。贪玩的小Z会一直游玩,直到当前景点的相邻景点都已经访问过为止。小Z所有经过的景点按顺序构成一条非重复路径,他想知道这条路径的期望长度是多少?

小Z把游乐园的抽象地图画下来带回了家,可是忘了标哪个点是大门,他只好假设每个景点都可能是大门(即每个景点作为起始点的概率是一样的)

同时,他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点

Read More

扩展欧几里得算法与中国剩余定理

在《孙子算经》中有这样一个问题:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

这个问题说的是,有一件物品,我们不知道它的数量。但是,如果三个三个数,最后会剩下两个;如果五个五个数,最后会剩下三个;如果七个七个数,最后会剩下两个。问这个东西的数量是多少?

实际上,这个问题在现在我们可以将其转化为一个同余方程组:

 \left\{ \begin{aligned} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \\ x \equiv 2 \pmod 7 \end{aligned} \right.

中国剩余定理告诉了我们像这样的同余方程组的解。这个定理又称为孙子定理,通常被简写成CRT(Chinese Remainder Theorem)。

这篇文章将会从欧几里得算法开始讲起,之后过渡到扩展欧几里得算法解线性方程,最后介绍中国生于定理。

Read More