codevs 1999 模积和 题目不是很难，但取模比较繁琐，为此 WA 了两遍。 题目大意求：$$ \sum_{1 \leq i \leq n & 1 \leq j \leq m & i \neq j} (n % i)(m % j) $$ 设 $t = \min(n, m)$ ...

AC自动机是一个建立在字典树上的算法，可以在线性时间复杂度内完成多字符串匹配。 我们对于所有匹配字串建一颗字典树，接下来，参考 KMP 算法，我们建立一个 fail 指针，相当于 KMP 的 next 数组，表示我们在失配时跳转到的结点。 参考 next 数组的求法，我们可以在对字典树进行广度优先搜 ...

今天上午考了一次试，有三道题，整理一下。 本次试题链接 第一题大意为给你 $n$ 个数，你需要求出每对数相异或的和(此处需要注意的是 $(a, b)$ 和 $(b, a)$ 为同一对)。 对于这道题，我们可以把每个数拆分成几个二进制位，对于第 $i$ 位，统计所有数的第 $i$ 位的值进行求和，放 ...

为了填充自己空荡荡的博客，打算写题…. 题目背景SDOi2012 题目描述 Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数 $N$ ，你需要求出$\sum\limits_{i = 1}^ngcd(i, n)$。 输入输出格式 输入格式：一个 ...

线段树是一个能在 $O(logn)$ 的时间复杂度内进行区间修改和区间查询操作的数据结构。非常神奇！ 建树操作考虑如何构建一颗线段树： 我们对于一个区间 $[l, r]$ ，我们将其分为两个子区间 $[l, mid]$ 和 $[mid + 1, r]$ ，其中 $mid = \frac{l + r ...

ST 表是一个在 O(nlogn) 时间复杂度预处理后在允许在 O(1) 的时间内查询区间最大最小值的，额，方法，或数据结构。一个非常神奇的算法。 预处理部分我们需要预处理一个 $st$ 数组，$st[i][j]$ 则代表序列第 $i$ 位开始向后 $2^j$ 位的最大值。 这个预处理我们很显然可以 ...

我们谈一下 kmp 算法的思想与实现。 kmp 算法是一个在 O(n + m) 的时间复杂度下实现的字符串匹配算法。说道 O(n + m) 的字符串匹配，大家肯定很自然地想到 hash ，如果利用 hash 的话很轻易就实现了在 O(n + m) 的时间复杂度内匹配字符串了，但是，如果字符串本身很 ...

数论基础作为一门研究整数性质的哲学，数论在 OI 中还是很受欢迎的，它凭借着它别具一格的特色和令人…… 我编不下去了，开始研究数论。。 一些小知识 若 $b % a = 0$ 即 $b = ka$ ，则我们成 $a$ 整除 $b$ ，记作 $a | b$ 。 若 $a | b$ ，则我们称 $a$ ...