Loading...
博主已经退役,评论可能会审核很久才能通过。
本文被密码保护。如果想知道密码请联系博主。
QwQ
Luogu UOJ 分析 求出 $s$ 的所有周期 $l_1, l_2, \cdots, l_k$,那么我们相当于要求有多少个 $x \in [0, w - n]$ 满足存在一组 $\{x_i \geq 0\}$ 使得 $\sum_{i = 1}^k x_i l_i = x$。 发现如果 $x$ 可以,那么 $x + n$ 也一定可以,于是我们可以在模 $n$ 意义下跑同余类最短路(这里最短...
Codeforces 分析 这个数量平方的异或和感觉没有什么性质,那么我们只能想办法对每个集合求出数量。 一个想法是先预处理出集合大小为 $1$ 时的数量,然后做子集和,但是这样子会算重:对于 $abc$,$ab$ 处将其计算了两次。 于是考虑容斥:我们在 $a, b, c$ 处加 $1$,$ab, ac, bc$ 处减 $1$、$abc$ 处加 $1$,那么这样子做子集和求出来的数量就是正...
阶与原根 阶 定义 1.1 (阶) 对于 $m \in \mathbb{N}^*, a \in [0, m), (a, m) = 1$,设 $n$ 为满足 $a^n \equiv 1 \pmod{m}$ 的最小正整数,则称 $n$ 为 $a$ 模 $m$ 的阶,记做 $\delta_m(a)$。 关于阶,我们给出如下定理: 定理 1.1 $a, a^2, \cdots, a^{\del...
Codeforces 分析 我们可以把题目中的过程看成二维网格上的游走,即每步可以向下或向右下走,代价为该列的权值,求从第一行走到 $(x, y)$ 的最短路。 注意到这样的最短路一定是先往下走若干步,然后往右下走到终点。因此设 $s$ 为 $a$ 的前缀和,那么从 $(1, i)$ 走到 $(x, y)$ 的最短路为 $s_y - s_i + a_i(x - y + i)$。我们要对每个询...
Codeforces 分析 这种奇奇怪怪的生成树题考虑 Boruvka 算法。其核心思想是对每个连通块找到最近的连通块,然后合并。 对于这道题,我们考虑把所有数插入到一棵 Trie 中,那么对于每个节点,其左子树和右子树中必定只由一条边相连。这是因为在执行 Boruvka 算法的过程中,必定是左右子树先分别连通,然后再通过一条边合并在一起。 那么我们只需要知道两个数组间两两异或的最小值,将一...
Codeforces 分析 orz yhx 为了方便我们在最后加一个 $a_i = N, b_i = N, c_i = +\infty$ 的站台,其中 $N$ 是一个很大的数。这样子我们可以保证每辆火车恰好送走 $k$ 个人。 设 $f_{i, j}$ 表示只考虑前 $i$ 个站台、要坚持 $j$ 时刻最少需要放多少辆火车,$g_{i, j}$ 表示只考虑前 $i$ 个站台、要坚持 $j$ ...