Miskcoo's Space

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

离散对数(Discrete Logarithm)问题是这样一个问题,它是要求解模方程 \[a^x \equiv b \pmod m\] 这个问题是否存在多项式算法目前还是未知的,这篇文章先从 $m$ 是质数开始介绍大步小步法(Baby Step Giant Step)来解决它,之后再将其应用到 $m$ 是任意数的情况。这个算法可以在 $\mathcal O(\sqrt m)$ 的时间内计...

BZOJ-3812. 主旋律

题目给出一个 $n$ 个点,$m$ 条边的有向图,要求求出删掉一些边以后,整个图强联通的方案数,其中 $n \leq 15, m \leq n(n-1)$ 样例是这样的,十分良心,一共有 $9390$ 种方案 题目链接:BZOJ-3812 这是陈老师的神题,一直纠结了我三四天才会做(你可以在他 WC2015 讲课的 PPT 上找到这题的题解) 首先看到数据范围很容易想到的是可...

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

给定正整数 $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...

多项式求逆元

概述 多项式求逆元是多项式除法和多项式取模的必要过程,在竞赛中,有时候多项式求逆元的应用比多项式的除法还要多,用快速傅里叶变换以及倍增算法可以做到在 $\mathcal O(n\log n)$ 的时间内求出一个多项式的逆元 基本概念 在介绍多项式的逆元之前,先说明一些概念:多项式的度、多项式的逆元、多项式的除法和取余 对于一个多项式 $A(x)$,称其最高项的次数为这个多项式的度(degr...

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$,那么 $abc$ 在 $s_1$ 中出现过,$a$ 在 $s_1, s_...

BZOJ-4001. [TJOI2015]概率论

题目要求出一个含有 $n$ 个节点的有序二叉树的叶子节点的期望个数,$n \leq 10^9$,要求精确到 $1.0 \times 10^{-9}$ 例如一个含有 3 个节点的二叉树,一共有 5 种情况,期望的叶子节点个数是 $\frac{6}{5}$ 首先可以用 $H_n$ 表示有 $n$ 个节点的二叉树的个数,空树没有节点,因此 $H_0=1$ 考虑一棵有 $n$ 个节点的...

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 < k$ 且 $a_i - a_j = a_j - a_k$ 也就是统计有多少对长度为 $3$ 的等差子序列(题目连接 BZOJ-3509, CodeChef COUNTARI...

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

概述 计算多项式的乘法,或者计算两个大整数的乘法是在计算机中很常见的运算,如果用普通的方法进行,复杂度将会是 $\mathcal O(n^2)$ 的,还有一种分治乘法可以做到 $\mathcal O(n^{\log_23})$ 时间计算(可以看这里)。下面从计算多项式的乘法出发,介绍快速傅里叶变换(Fast Fourier Transform, FFT)如何在 $\mathcal O(n\l...

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$ ...

区间K小问题

无修改、无插入区间第K小问题 关于这题,可以直接用主席树(函数式线段树)来解决。假设现在有无限的内存和时间,可以对每个前缀构造一棵权值线段树,然后每次询问区间 [l, r] 就找出前缀 [0, l - 1] 和 [0, r] 的线段树,相减就可以得到所需要的权值线段树,然后在这上面根据子树大小跑就可以了。 由于空间有限,最开始不初始化整棵树,而是动态的添加节点,并且在插入的时候只有经过的...