Loading...
如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。
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$ ...
Luogu 分析 首先考虑给你两个圆怎么算交的面积。 设两圆心距离为 $d$，可以算出交弦所对的圆心角 $\theta = 2\arccos \frac{d}{2r}$，然后两个扇形的面积为 $\theta r^2$、菱形的面积为 $\sin\theta r^2$，因此交面积为 $(\theta - \sin\theta)r^2$。 考虑 DP。设 $f_{i, j}$ 表示前 $i$ 个圆...
Luogu LOJ 分析 orz myy 可以发现，一条回文路径左右扩展一个相同字符仍然是一条回文路径。 设 $f_{u, v}$ 表示 $(u, v)$ 间是否存在一条回文路径，转移枚举出边即可。这样子是 $\mathcal{O}(m^2)$ 的。 因为我们可以在一条边上反复横跳，所以直觉上这个东西只会和奇偶性有关。 对于连接同色点的边，我们对每个连通块单独考虑：如果构成二分图，则可以只保...
Luogu LOJ 分析 可以发现第 $i$ 个点有 $i$ 个位置可以插入，所以不同的树的个数为 $n!$，因此题目要求的就是所有树的答案总和。 如果只考虑一棵树，有一个经典的做法：考虑每个点父边的贡献，为两端点数之积 $sz \times (n - sz)$。 我们考虑枚举一个点 $i$ 和其子树大小 $k$，然后计算多少棵树中有这样的边。 首先，我们需要插入 $[1, i]$ 中的点，...