- 本文为 Apostol 的 Introduction to Analytic Number Theory 的第 11 章的学习笔记。 - 这**不是** OI 相关内容，但如果你正在学习 DGF（狄利克雷生成函数），文中部分内容可能对你有用。 ### 记号与引入 形如 $\displaystyle\sum_{n =…

在文章《CCPC2025济南站被翻盘记》发表评论：

我要看 CTT2025 监考员游记 /se

在文章《CQ高考游记》发表评论：

煮波好牛，拜谢煮波。诵读“考完感觉每一科都很简单”。高考出分前我还在焦虑自己是不是需要复读来着（

~~感觉这题很 hard。~~ ----- 注意到任意一条劣弧的长度的上确界为 $\lfloor \dfrac{n}{2} \rfloor$。 为了获取所求弦的信息，考虑构造一个劣弧尽可能长的点对 $(u, v)$，然后让它对应的最短路**一定**经过所求弦。 注意到不经过所求弦的情况仅可能是所求弦“近乎”被 $(u,…

一个自然的想法是： - 枚举 $S$ 表示 character card 里有啥，$T$ 表示 music card 里有啥。 - 要求 $\forall i \in [1, k], (a_i \in S, b_i \in T) \lor (a_i \in T, b_i \in S)$。 - 满足条件时，对答案产生 $…

背景信息：pku 的“注意到不难发现”队，队长 [cqbzly](https://www.luogu.com.cn/user/308010)，另一位队员是 [nKessi](https://www.luogu.com.cn/user/312398)。~~我则负责提供饮食保障和情绪价值。~~ 这里就直接 Day 2（正式…

### 算法一 一个最为暴躁的想法是： - $\forall i \in [1, k], 1 \leq p #include using namespace std; typedef long long ll; int cnt[200001], *a[200001], L[200001], R[200001], bel…

感觉这题好神秘啊。 ------ 我们需要选出 $\{[L_i, R_i]\}$ 使得 $L_1 = 1, R_m = n, \forall i \in [1, m) \cap \mathbb{Z}, L_{i + 1} - R_i = 1$，可以将 $[L_i, R_i]$ 合成一段，并最大化 $\displayst…

这个 $\lfloor \dfrac{n^2}{a} \rfloor$ 的限制看上去很神秘啊！但为什么会是这样呢？ 设这 $a$ 个能用的电池位于 $x_1 \sim x_a$（不妨使 $\{x_i\}$ 单调递增），则由抽屉原理可知 $\min(x_{i + 1} - x_i) \leq \lfloor \dfrac…

呜呜呜，被“中档题”杀害了。 ------ 首先不难给出一个给定 $n$、求出轮数的“暴力”算法： - 若现在有 $n$ 个人，则一轮后还剩 $n - \lceil \dfrac{n}{k} \rceil$ 个人。 - 考虑将 $\lceil \dfrac{n}{k} \rceil$ 相同的轮次合并处理，显然它们是连续…

注意到若从后到前遍历 $j = r, r - 1, \cdots, l$，我们可以将 $a_j$ 改为 $\{a_i \mid l \leq i \leq j\}$ 的任意子集（可以为空）的异或值。 设值域 $w = 2^{20} - 1$，则一个显然的 $O(\sum qn \log w)$ 暴力是： - 从 $l$…

$n$ 为奇数时显然无解，下面讨论 $n$ 为偶数的情况。 考虑我们可以拿这样的神秘操作干些啥： - 最直接的是：如果我们有一些 `((`，可以将其换成 `))`，反之亦然。 - **我们能移动这样的连续括号吗？** - 不难发现是可以的：`(()` 可以变成 `)))`，再变成 `)((`，我们事实上将 `((` 移…

在讨论《增加一组Hack》回复：

@[_•́へ•́╬_](luogu://user/90693) 我和验题人都没想过这题会有 $O(\sum n^2)$ 做法，我的问题 /fad

在讨论《增加一组Hack》回复：

@[zhangzihan2029](luogu://user/925752) 我已无法更改此题数据，建议开工单让管理员来处理。

不难发现我们可以逐层（即分不同的 $z$ 坐标）讨论，然后把答案加起来。 此时我们要选一些 $(i, j)$，使得： - 对于所选的 $(i, j)$，$a_{z, i}, b_{z, j}, c_{j, i}$ 均为 $1$。 - $\forall a_{z, i} = 1$，选了至少一个 $(i, j)$。 - $…

题意即数一棵树的重心唯一的联通子图数量。 重心唯一不好算，考虑转化为有两个重心，我们知道这两个重心是相邻的。 由重心为根时，所有子树的大小都不超过整棵树大小的一半的性质，我们不难发现：**相邻中心两侧子树大小相等**。 因此就有一个自然的想法： - 设 $f_{u, i}$ 表示在 $u$ 子树内选出一个包含 $u$、…

## 基本定义与性质 **网络**：一张**有向图** $G = (V, E)$，每条边 $(u, v) \in E$ 有**容量** $c(u, v)$。对于不在 $E$ 中的 $(u, v)$，我们认为 $c(u, v) = 0$。 **可行流**： - 有**流函数** $f : (u, v) \to \math…

## 定义 对于一张**无向图** $G = (V, E)$，定义： - $M \subseteq E$ 为 $G$ 的一个**匹配**，当且仅当 $M$ 中的边两两没有公共顶点。 - $M$ 的**大小**指其中包含的边数。 ------ - 匹配点：作为匹配中某条边的两个顶点之一的顶点。 - 最大匹配：大小最大的匹…

考虑枚举一个**极长颜色段** $[l, r]$ 并统计其贡献，则要求是： - $a_l = a_{l + 1} = \cdots = a_r$。 - $a_l \neq a_{l - 1}, a_r \neq a_{r + 1}$。 前者看上去相对便于处理，但后者看上去非常让人难受 /ll 考虑去掉这一限制。设有系数…

在讨论《「WWOI」Round 1 赛后总结帖》回复：

@[WsW_](luogu://user/349824) 啊？我写的是传统序列哈希，没注意题解写的啥（

在讨论《「WWOI」Round 1 赛后总结帖》回复：

@[WsW_](luogu://user/349824) A（橙）：感觉有点意思，但官方题解是不是做复杂了？答案应该就是 $2^{b - \max(a, \lfloor \frac{b}{k} \rfloor + 1) + 1}$。 B（黄 - 绿）：感觉这个哈希没有太多新意？虽然写起来确实有点细节（ C（绿）：感觉这…

方便起见，先将 $a[1 \sim n]$ 离散化映射到 $[1, n]$ 中的整数。 --- 一个想法是直接维护排序过程中的递增连续段，但看上去不太能做 /ng - **排序不会做？不就是 $\forall x \in [1, n], \{[a_i > x]\}$ 这 $n$ 个 01 数列都排好序了吗？** 考虑如…

非常好划分数 dp 练习题，使 vp 时的我的大脑旋转 /yun ------ ~~随手写个对 $a$ 计数的 dp~~ 发现：同一个 $Q$ 可能对应很多个 $a$。 - 如：$Q = \{2\}$ 时 $a$ 可能有 $\{1, 1, 1\}, \{2, 2\}$ 两种选项。 那我们能否指定某一种 $a$，使得所有…

首先注意到 `docker` 没有相同的真前缀和真后缀，这意味着我们可以视其为独立的一坨。 去除区间中 $> \frac{|s|}{6}$ 的部分，差分求出最优的一些可选项。 设初始 $s$ 中有 $x$ 个 `docker`。 若可选项中有不大于 $x$ 的，设其最大值为 $y$，则我们只需选取 $x - y$ 个…

下称「雪」为 Alice，「K」为 Bob。 --- 考虑二分，将问题转化为： - 给定 $01$ 序列 $b$，问最后剩下的数是否为 $1$。 ~~一个显然的想法是区间 dp，但二分完再这样就不如纯暴力了。~~ 考虑最简单的情况：$b$ 由连续的 $x$ 个 $0$ 和 $y$ 个 $1$ 拼起来。 - $x = y…

赛时被 $s \leq 17$ 骗了（ ------ 有解时，由于 $i$ 有 $n - 1$ 种选法，显然有 $s 2$ 的方案吗？** 若 $a_{p + 1} > \frac{S}{2}$，可直观理解为“别人拼尽全力也无法消掉它”，此时一定不行。 综上，有解时 $s \leq 2$。代码实现较为简单。 代码： `…

在讨论《hack》回复：

@[changziliang](luogu://user/427064) 请给出被 Hack 的代码及正误输出。

在讨论《LACPT-Open 题单征集》回复：

~~退役人来投点自己出的题。~~ - [P9091 「SvR-2」Let's Meet at a Higher Place](https://www.luogu.com.cn/problem/P9091)：筛子。 - [P9307 「DTOI-5」进行一个排的重 (Maximum Version)](https://w…

在讨论《CSP 2023 游记集合贴》回复：

https://www.luogu.com.cn/blog/Leasier/CSP-S-2023-Travel-Note

在讨论《hack》回复：

@[览遍千秋](/user/28910) 这组数据不满足数据范围，数据范围中保证了 $n \geq 5$。