• 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 2 = 1, d \bmod 4 = 1$

    题目连接:BZOJ-4002(这里的题面不完全,我上面打出来的是完整的)

  • 多项式求逆元

    概述

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

  • 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_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

  • BZOJ-4001. [TJOI2015]概率论

    题目要求出一个含有 $n$ 个节点的有序二叉树的叶子节点的期望个数,$n \leq 10^9$,要求精确到 $1.0 \times 10^{-9}$

    例如一个含有 3 个节点的二叉树,一共有 5 种情况,期望的叶子节点个数是 $\frac{6}{5}$

  • 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

    例如 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 对

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

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

  • 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
  • 区间 K 小问题

    这篇文章将会介绍如何求解区间 K 小问题。

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

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

  • BZOJ-3267. KC采花

    这题是 bzoj-3267 上的题目,原题大概是给一列数,要求支持操作:

    • 修改某个数的值
    • 读入 l、r、k,询问在 [l,r] 内选不相交的不超过 k 个子段,最大的和是多少

    然后序列的长度和操作的次数大约都在 $10^5$ 级别的