• May 13, 2015

    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（这里的题面不完全，我上面打出来的是完整的）

  • May 10, 2015

    多项式求逆元

    概述

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

  • May 1, 2015

    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-2780、SPOJ-JZPGYZ

  • Apr 29, 2015

    BZOJ-4001. [TJOI2015]概率论

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

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

  • Apr 27, 2015

    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 对

  • Apr 25, 2015

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

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

  • Apr 23, 2015

    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
  • Apr 5, 2015

    区间 K 小问题

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

  • Apr 5, 2015

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

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

  • Dec 10, 2014

    BZOJ-3267. KC采花

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

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

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