May 2015 – Miskcoo's Space

平面图转对偶图及点定位

May 29, 2015August 19, 2017 miskcoo 1 Comment

平面图（planar graph）就是一个可以在平面上画出来的图，并且所有的边只在顶点处相交。平面图的对偶图（dual graph）是将这个平面的每个区域看成点，原图每一条边所属的两个相邻的区域对应在对偶图中的点有连边

比如下面这张图（来源于 Wikipedia）

蓝色的部分就是一个平面图，红色的就是它的对偶图

平面图的点定位（point location）就是找出一个点属于这个图的哪个区域

这篇文章介绍如何将一个平面图转换为其对偶图，和基于扫描线的离线的点定位算法（对着代码看了一天终于会了QAQ）

BZOJ-3456. 城市规划

May 28, 2015August 19, 2017 miskcoo 4 Comments

题目要求求出有 $n (n \leq 130000)$ 个点的有标号简单连通无向图的个数，答案 $\bmod 1004535809$ $(479 \times 2^{21} + 1)$ ，是个质数

比如三个点的情况

graph-3node

题目链接：BZOJ-3456

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

May 25, 2015July 25, 2019 miskcoo 15 Comments

多项式的多点求值（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)$ 的之间内将两种东西互相转换，但是，如果是任意给定点要求求值或者插值，就没有比较好的性质可以利用，但是仍然有比较快速的方法来计算它们

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

May 23, 2015August 19, 2017 miskcoo Leave a comment

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

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

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

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

【输入格式】

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

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

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

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

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

【输出格式】

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

【数据范围】

$n \leq 10^5$ ， $1 \leq c_i \leq 10^4$ ， $a_i \leq 2\times 10^9$ ， $r_i \leq 10^9$ ，时限 12s

多项式除法及求模

May 22, 2015August 19, 2017 miskcoo 3 Comments

问题是这样的：给定一个 $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 - m$ ， $degR < m$

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

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

BZOJ-3557. [Ctsc2014]随机数

May 21, 2015August 19, 2017 miskcoo 1 Comment

这是 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 > 1$ 时 $x=0$ 就显然不是好的。

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

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

【输入格式】

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

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

$type = 0$ （萱萱记下了花花的输入）：则第五行包含一个整数，表示萱萱记下来的正确的 $k$ 值。
$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 10$ ， $x$ 是“好的”

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

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

May 16, 2015August 20, 2017 miskcoo 17 Comments

离散对数（Discrete Logarithm）问题是这样一个问题，它是要求解模方程

$a^x \equiv b \pmod m$

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

题目链接：BZOJ-2480、SPOJ-MOD、BZOJ-3239

BZOJ-3812. 主旋律

May 16, 2015August 19, 2017 miskcoo 1 Comment

题目给出一个 $n$ 个点， $m$ 条边的有向图，要求求出删掉一些边以后，整个图强联通的方案数，其中 $n \leq 15, m \leq n(n-1)$

样例是这样的，十分良心，一共有 $9390$ 种方案

bzoj-3812-sample

题目链接：BZOJ-3812

BZOJ-4002. [JLOI2015]有意义的字符串

May 13, 2015August 19, 2017 miskcoo 3 Comments

给定正整数 $b, d, n$ ，计算

$\left \lfloor \left (\frac{b + \sqrt d}{2}\right )^n \right \rfloor \bmod 7528443412579576937$

其中 $0 < b^2 \leq d < (b + 1)^2 \leq 10^{18}, n \leq 10^{18}$ ，并且 $b \bmod 2 = 1, d \bmod 4 = 1$

题目连接：BZOJ-4002（这里的题面不完全，我上面打出来的是完整的）

多项式求逆元

May 10, 2015August 19, 2017 miskcoo 14 Comments

概述

多项式求逆元是多项式除法和多项式取模的必要过程，在竞赛中，有时候多项式求逆元的应用比多项式的除法还要多，用快速傅里叶变换以及倍增算法可以做到在 $\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)}$