dropconst

摘要： https://www.luogu.com.cn/problem/P3232 记 \(E_u\) 为点 \(u\) 的期望经过次数，\(d_u\) 为度数，则 \[E_u = \sum_{v \in N(u)} \frac{E_v}{d_v} \]高斯消元即可。边 \(uv\) 的期望经过次数即为 阅读全文

摘要： https://hydro.ac/p/bzoj-P3560 设 \(b_{p, i}\) 为质数 \(p\) 在 \(a_i\) 中的指数，\(e_{p, i}\) 为选出的指数，则 \[\begin{aligned} \sum_{d_1 \mid a_1} \cdots \sum_{d_n \mi 阅读全文

摘要： https://hydro.ac/p/bzoj-P4804 \[\begin{aligned} \sum_{i = 1}^n \sum_{j = 1}^n \varphi(\gcd(i, j)) &= \sum_{d = 1}^n \varphi(d) \sum_{i = 1}^n \sum_{j 阅读全文

摘要： https://www.luogu.com.cn/problem/P2398 \[\sum_{i = 1}^n \sum_{j = 1}^n \gcd(i, j) = \sum_{i = 1}^n \sum_{j = 1}^n \sum_{d \mid \gcd(i, j)} \varphi(d) 阅读全文

摘要： https://codeforces.com/problemset/problem/165/E 等价于求 \(a_i\) 按位取反后的子集和，预处理高维前缀和即可。 阅读全文

摘要： https://www.luogu.com.cn/problem/P4151 答案一定由一条 \(1\) 到 \(n\) 的路径和若干以路径上点为起点的闭途径组成，而闭途径的 XOR 一定可以表示为若干环的 XOR。因此，只需找出一条 \(1\) 到 \(n\) 的路径和所有环，线性基求出路径与环的 阅读全文

摘要： https://www.luogu.com.cn/problem/P2414 建出 AC 自动机，记 \(ed_i\) 为第 \(i\) 个串在 Trie 上的终止节点，则第 \(x\) 个串被第 \(y\) 个串包含的次数为 \(ed_y\) 到根的所有点中，在 fail 树上 \(ed_x\) 阅读全文

摘要： https://codeforces.com/problemset/problem/843/D 先跑一遍 Dijkstra，由于 \(dis\) 的增量不超过 \(c\)，将边权设为 \(dis_u + w - dis_v\)，用容量为 \(c\) 的桶代替堆跑 Dijkstra 求出最小增量即可。 阅读全文

摘要： https://hydro.ac/p/bzoj-P2969 将答案拆成每个位置被刷的概率之和，\(P(\text{位置 } (i, j) \text{ 被刷}) = 1 - P(不被刷) = 1 - P(单次不被刷)^k = 1 - (1 - P(单次被刷))^k\)，将行和列分开考虑即可。 阅读全文

摘要： https://hydro.ac/p/bzoj-P2396 随一个 \(1 \times n\) 的矩阵 \(D\) 判断 \(DAB\) 是否等于 \(DC\)，多随几次即可。时间复杂度 \(O(n^2)\)。 阅读全文