本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-25 22:27:32

:::::info[题目基本信息] 考察：动态规划 DP（个人认为是紫，也可能是我太菜了）。
题目简介：
给定 $\{op_n\}$，值域为 $\{0,1,2,3\}$，问有多少 $n$ 阶排列满足（对 $998244353$ 取模）：

• $\displaystyle\forall i\in(1,n],op_i=0\Rightarrow a_i<\min_{j=1}^{i-1}a_j$
• $\displaystyle\forall i\in(1,n],op_i=1\Rightarrow a_i>\max_{j=1}^{i-1}a_j$
• $\displaystyle\forall i\in[1,n),op_i=2\Rightarrow a_i<\min_{j=i+1}^na_j$
• $\displaystyle\forall i\in[1,n),op_i=3\Rightarrow a_i>\max_{j=i+1}^na_j$

数据范围：

• $1\le n\le 5000$
• $\forall i\in[1,n],op_i\in\{0,1,2,3\}$ ::::: 对于排列，套路地上连续段 DP，套路地设 $f_{i,j}$ 表示考虑到 $a_{pos}\in[1,i]$ 的所有 $pos$，它们形成了 $j$ 个连续段，至于状态细节不必管，反正最后我尝试的状态都寄了。
  那咋办？！？！？！
  :::::info{open} 不只尝试改变连续段的定义，还要尝试改变连续段定义于的对象。谁告诉你连续段 DP 只能对值域 DP 的？
  切记 DP 题不是套板子题。
  如果你看不懂下面的内容就在心里默念：连续段 DP 是在相对位置上进行 DP，并手玩验证每一种方案都能构造出实例。 ::::: 尝试改变状态的定义，设 $f_{i,j}$ 为考虑到 $[1,i]$ 的所有 $pos$，未被考虑的位置可以在 $j$ 个值域连续段（中间没有已填位置的段）填，先判掉无解情况（存在一个 $2$ 位于 $0$ 左边或者存在一个 $3$ 位于 $1$ 左边），接下来分类讨论：
• $op_i\in\{0,1\}$：
  这时该元素不会对后面的元素造成影响，还会凭空增加一个连续段，所以 DP 数组会整体平移。
• $op_i\in\{2,3\}$：
  这时手玩发现这个位置左右至少有一边位置不能填了，这样会使连续段数量变少（可以不变），所以 DP 数组会整体求后缀和。

按上述简单实现可以通过。
时间复杂度为 $\Theta(n^2)$，空间复杂度为 $\Theta(n)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-26 22:31:29

:::::info[题目基本信息] 考察：搜索，图论（中下位紫？）。
题目简介：
给定 $n$，有 $n$ 个物品，价值为 $\{w_n\}$，两端（可以钦定哪端是首段，哪端是尾端）颜色分别为 $\{s_n\},\{t_n\}$，现在你需要选取一些物品，将它们按任意顺序排列，将它们拼接，要求拼接的相邻物品中前一个物品的尾端颜色和后一个物品的首端颜色相同，你的得分就是选取的物品的价值总和，问得分最大是多少。
数据范围：

• $1\le n\le 5\times 10^5$
• $\forall i\in[1,n],1\le w_i\le 1000$
• $\forall i\in[1,n],1\le s_i,t_i\le\color{red}4$ ::::: 见二连边还在追我，容易想到对于每一个物品连一条 $s_i\leftrightarrow t_i$ 的边，然后你观察到里面有很多很多的重边，考虑怎么利用。
  有一个比较重要的性质：
• $\forall u,v$，$u$ 和 $v$ 之间的无向边在两点均可达时可以两两缩成一个点的自环，直到还剩最多两条边。
  :::::success[证明] 这个性质是比较显然的。因为两条边就足够你来回一次了，剩下的边自然可以缩成一个自环单独处理。
  ::::: 然后我们注意到对于所有可达点自环都能被记进贡献内（注意当原图就有多条自环时同样需要根据上面方式保留最多两条边），然后发现对于剩下的边我们可以直接爆搜，于是就有了下面的算法流程：
• 枚举点集子集，使用并查集判断它们是否联通，若不联通枚举下一个子集。
• 对于一个子集先累加自环贡献，然后对于剩余的边直接爆搜所有路径即可。

:::::success[优化] 在爆搜中，对于一个点，我们对于通向同一个点的边只选择价值最大的那条递归，容易证明正确性，实测运行时间缩小到原来的 $\dfrac{1}{60}$。
::::: 这样我们就做完了此题。
时空复杂度玄学。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-29 19:41:02

保证本文中笔者贡献不高于 GenAI。
保证本文中批话占比不低于 20%。

CSP-S：

请勿指责，已被 Pigsyy 彻底击败，自身实力尚有不足，故不打算撰写游记。

NOIP 前一天：

下午抵达淄博后，立即投入模板练习，但面对缩点、割点、二边连通分量等概念仍感困惑，不禁自嘲基础薄弱。
晚间进行试机准备，认真调试了线段树模板。随后，我进行了如下操作（此前一直未明确 Linux 的具体位置）：

• 首先根据老师指引找到虚拟机软件，在左下角菜单中搜索以 V 开头的程序，成功定位。
• 启动虚拟机后，打开 CodeBlocks 编辑器，编写测试代码并尝试编译，经过摸索最终顺利完成。

试机流程按计划结束，随后休息。虽感自身水平有待提升，但仍需调整心态迎接明日挑战。

NOIP：

开题。
T1 初步尝试后迅速调整思路，冷静处理后成功通过，此时已耗时近一小时。出考场后得知多数人仅用数分钟便解决 T1，不禁感叹自身差距。
T2 经过约数小时严谨推导，得出 $\Theta(n^3)$ 解法，但因实现复杂度较高而放弃，转而争取部分分数。
T3、T4 获得常规得分。
整体表现平平，再次反思自身不足。出考场后发现 KSCD_ 成绩显著领先，更感自身需提升。
返家后查阅资料，发现 T4 实为一道曾做过的题目之强化版本，原题可获 85 分，对此深感遗憾。

:::::success[总结] 我咋这么菜。
:::::

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-17 15:33:54

:::::info[题目基本信息] 考察：图论，贪心，线段树（$3300$）。
题目简介：
给定 $\{a_n\}$，求 $m$ 的最大值使得存在 $m$ 个三元组 $(x_i,y_i,z_i)$ 满足：

• $\forall i\in[1,m],1\le x_i<y_i<z_i\le n$
• $\forall i\in[1,m],a_{x_i}=a_{z_i}=0,a_{y_i}\ne 0$
• $\forall i,j\in[1,m],i\ne j,a_{y_i}\ne a_{y_j}$
• $\forall i,j\in[1,m],i\ne j,\{x_i,y_i,z_i\}\cap\{x_j,y_j,z_j\}=\arnothing$

数据范围：

• $1\le n\le 5\times 10^5$
• $\forall i\in[1,n],0\le a_i\le n$ ::::: $m$ 的取值显然具有可二分性，考虑先二分。
  每一个元素权值三元组都是 $(0,x,0)$ 的样子，贪心地想，我们肯定会让位于三元组左边的 $0$（下文简称左 $0$）尽可能的靠左，右边的（下文简称右 $0$）尽可能的靠右，所以每当有一个右 $0$ 位于左 $0$ 的左边那么我们交换他们肯定不劣，所以我们令前一半 $0$ 是左 $0$，后一半 $0$ 是右 $0$。
  现在我们考虑对每一个颜色（$a$ 序列）建一个左部点，对每一个相对位置（$1$ 到 $m$）建一个右部点，那么颜色 $col$ 连向相对位置 $pos$ 当且仅当：
• $\exists i\in[1,n]$ 满足：
  • $a_i=col$
  • $\displaystyle\sum_{i=1}^{pos-1}[a_i=0]\ge pos$
  • $\displaystyle\sum_{i=pos+1}^n[a_i=0]\ge n-pos+1$

直接暴力跑匹配可以做到 $\Theta(n^{2.5}\log n)$ 的复杂度，但是和正解几乎一点关系没有。
我们考虑观察一下一个颜色所连的点有什么特点，注意到一个位置要么左 $0$ 全在他的左边，要么右 $0$ 全在他的右边，那么分别只需要满足 $\displaystyle\sum_{i=1}^{pos-1}[a_i=0]\ge pos$ 和 $\displaystyle\sum_{i=pos+1}^n[a_i=0]\ge n-pos+1$ 即可，那么对于任意一个位置，他可以作为一段前缀或一段后缀，那么全部并起来就会变成一段前缀和一段后缀。
唉这不就是 ARC076F 吗，那个题的时间复杂度是 $\Theta(n\log n)$ 的（具体见 我的题解），那么我们的时间复杂度是 $\Theta(n\log^2n)$ 的，可能能过去但是我被卡了。
然后我们考虑去掉二分的 log，我们注意到这个二分屁用没有，因为有多少右部点是不影响答案的，所以我们直接把二分扔掉，然后我们就解决了此题。

时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-17 23:11:51

:::::info[闲话]{open} 一个魔怔做法。
LCA Project 怎么只开 2s，把我的神秘复杂度做法卡掉了，生气了。
还有就是调题调爽了。
::::: :::::info[题目基本信息] 考察：搜索（暂无难度）。
题目简介：
给定 $n$ 个字符串 $\{s_n\}$，只由 A、C、G、T 组成，对于所有 $i,j\in[1,n]$ 询问 $s_i$ 能否变换为 $s_j$，变换规则为：

• 选择一个子串 A，将其替换为 TC。
• 选择一个子串 C，将其替换为 AG。
• 选择一个子串 G，将其替换为 CT。
• 选择一个子串 T，将其替换为 GA。
• 上面所有操作的逆操作。

数据范围：

• $1\le n\le 100$
• $\forall i\in[1,n],1\le |s_i|\le 5\times 10^4$ ::::: 注意到操作可逆，所以变换具有传递性和交换律，那么最终可以互相变换的会是一个大等价类内的元素。
  考虑将一个字符串串长最小的字符串作为一个等价类的代表，那么我们注意到一个定理：
• 若没有串长为 $L$（$L>1$）的字符串作为等价类代表，那么也没有 $L+1$ 的字符串作为等价类代表。 :::::success[证明] 考虑反证法，假设存在 $L+1$ 的字符串作为等价类代表。
  若串长为 $L$ 的字符串没有被作为代表，那么他最终被转化为了串长更小的字符串，那么我们将 $L+1$ 的字符串的一个串长为 $L$ 的子串转化掉就能得到一个串长更小的字符串，与条件矛盾，证毕。
  ::::: 由上述我们还可知，从串长为一个 $L$ 开始后面的字符串都不会存在字符串作为等价类的代表，打表可知串长最长的等价类代表串长为 $4$。
  那么我们考虑爆搜观察，从所有串长不超过 $4$ 的字符串开始选择一个字符扩展为两个字符，打出表后我们发现扩展到所有长度 $10$ 的字符串后任意一个长度不超过 $5$ 的字符串都存在一个长度不超过 $10$ 的能被其扩展到（别问怎么发现的，多试试就试出来了），所以我们考虑预处理时先从所有串长不超过 $4$ 的字符串开始扩展到所有长度不超过 $10$ 的字符串，然后对于每个 $s_i$ 一个一个字符累加，每当串长不小于 $5$ 那么就爆搜到能被长度不超过 $4$ 的字符串扩展到的长度不超过 $10$ 的字符串（这个需要记忆化），然后将其整体替换为这个长度不超过 $4$ 的字符串，然后它们都被转化为串长不超过 $4$ 的字符串，然后通过 map 和并查集等数据结构一通维护串长不超过 $4$ 的字符串的变换，然后你就暴力地魔怔地很慢地占用空间很大地代码也很长很难调地解决了这道题。

时空复杂度不想分析，就算分析出来了也跑不满。

提交记录（展示运行速度）
code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-19 09:18:59

:::::info[题目基本信息] 考察：拓扑排序，bitset（省选/NOI-）。
题目简介：
有 $n$ 个路牌和 $m$ 个城市，它们都位于实数坐标，其中每一个路牌都在任意一个城市的左侧，现在对于第 $i$ 个路牌第 $j$ 座城市给定它们距离的下取整值 $d_{i,j}$（但不一定正确），问你能选出最多多少的路牌使得路牌到城市的距离下取整值不矛盾，并构造一种方案，方案中路牌按你钦定的实数坐标（只要不与所给信息矛盾）从小到大输出。
数据范围：

• $1\le n\le 1000$
• $1\le m\le 200$
• $\forall i\in[1,n],j\in[1,m],1\le d_{i,j}\le 10^6$
• 保证最多能选出的路牌数量不低于 $\dfrac{n}{5}$。
  ::::: 保证最多能选出的路牌数量不低于 $\dfrac{n}{5}$ 这一条件引导我们考虑先随机一个 $u$ 并钦定它在最终的构造方案中（错误率有 $\dfrac{4}{5}$，为方便估计正确率我们可以将随机三次都错误的概率近似成 $\dfrac{1}{2}$）这样我们随机 $\Theta(1)$ 次就有很大概率随机到正确答案。
  设 $\Delta d_{i,j}$ 表示实际未下取整与 $d_{i,j}$ 的值的差（容易得到 $\Delta d_{i,j}\in[0,1)$），同时设 $x_i$ 表示路标 $i$ 的坐标，$y_j$ 表示城市 $j$ 的坐标， 我们容易得到：
  $$y_j-x_i-\Delta d_{i,j}=d_{i,j}$$ 这个式子中 $y_j$ 和 $x_i$ 的范围我们是一点也不知道，所以我们考虑消元消去它们。
  由于 $u$ 的这个式子我们钦定已经成立，所以我们考虑令 $i$ 所对应的式子和 $u$ 所对应的式子相减得到：
  $$\begin{aligned}a_{i,j}&=d_{i,j}-d_{u,j}\&=(y_j-x_i-\Delta d_{i,j})-(y_j-x_u-\Delta d_{u,j})\&=x_u+\Delta d_{u,j}-x_i-\Delta d_{i,j}\end{aligned}$$ 我们观察到我们只需要再找到另一个 $a_{i,j_2}$ 与其相减即可，为了令其计算出的都不是负数所以我们找到该值最小的 $idx_i$ 与其相减得到：
  $$\begin{aligned}b_{i,j}&=a_{i,j}-a_{i,idx_i}\&=(x_u+\Delta d_{u,j}-x_i-\Delta d_{i,j})-(x_u+\Delta d_{u,idx_i}-x_i-\Delta d_{i,idx_i})\&=\Delta d_{u,j}+\Delta d_{i,idx_i}-\Delta d_{i,j}-\Delta d_{u,idx_i}\end{aligned}$$ 那么 $b_{i,j}$ 的值域是多少呢？
  因为 $idx_i$ 能使得 $a_{i,idx_i}$ 最小，所以 $b_{i,j}\ge 0$，又因为 $\Delta d_{i,j}\in[0,1)$，所以 $b_{i,j}<2$，又因为 $d_{i,j}\in\mathbb Z$，所以 $a_{i,j}\in\mathbb Z$，进一步地 $b_{i,j}\in\mathbb Z$，所以最终 $b_{i,j}\in\{0,1\}$！
  现在存在 $b_{i,j}$ 不满足这个条件的 $i$ 一定不能放在答案里，那么我们对 $b_{i,j}$ 的定义式进行变形得到：
  $$\Delta d_{i,j}=\Delta d_{u,j}+\Delta d_{i,idx_i}-b_{i,j}-\Delta d_{u,idx_i}$$ 现在我们要开始填数了，定 $i$，要求每个 $j$ 都满足要求，由于 $\Delta d_{i,idx_i}$ 和 $\Delta d_{u,idx_i}$ 这两项与 $j$ 无关，可以当做定值，又由于 $\Delta d_{i,j}\in[0,1)$，那么我们就得到 $i$ 合法的充要条件：
  $$\text{D}{j\in[1,n]}(\Delta d{u,j}-b_{i,j})<1$$ 其中 $\displaystyle D_i(x)=\max_{i}(x)-\min_{i}(x)$。
  利用我们得到的 $b_{i,j}$ 的值域（$b_{i,j}\in\{0,1\}$），我们容易得到最终的条件：
  $$\max_{j\in[1,n],b_{i,j}=0}\Delta d_{u,j}<\min_{j\in[1,n],b_{i,j}=1}\Delta d_{u,j}$$ 设 $S_i=\{j|j\in[1,n],b_{i,j}=1\}$，那么构造的集合合法当且仅当里面所有的 $S_i$ 两两包含，否则条件会产生矛盾。
  这样这道题就简单了，给所有的满足 $S_i\subseteq S_j$ 的 $(i,j)$ 连边（建出双向边，即 $S_i=S_j$ 时只保留一个方向）然后跑拓扑排序，找到最长路即可。
  这时时间复杂度是 $\Theta(n^2m)$ 的，能过 $60$ 分。
  注意到 $S_i\subseteq S_j$ 这个条件可以使用 bitset 优化，那么时间复杂度会除以一个 $w$，就可以通过了。
  时间复杂度为 $\Theta(\dfrac{n^2m}{w})$，空间复杂度为 $\Theta(nm)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-19 11:32:38

:::::info[题目基本信息] 考察：二分图，基环树，线段树（个人认为上位紫）。
题目简介：
给定一个由 $n$ 个左部点（编号为 $0$ 到 $n-1$，保证 $n$ 是奇数）和 $m$ 个右部点（编号为 $0$ 到 $m-1$）构成的二分图，$i$ 号左部点和 $j$ 号右部点右边当且仅当 $\min((j-a_i)\bmod n,(a_i-j)\bmod n)=b_i$（其中 $\{a_m\},\{b_m\}$ 事先给定，且 $\bmod$ 运算结果取最小的非负整数），将边编号（按左部点编号从小到大为第一关键字，按右部点编号从小到大为第二关键字），并给定每条边的初始权值 $w_i$，有 $q$ 次操作，每次操作将编号为 $pos_i$ 的边的权值改为 $v_i$，求所有操作前及每次操作后的二分图最大权完全匹配（保证存在），可能强制在线。
数据范围：

• $1\le m\le n\le 5\times 10^5$
• $\forall i\in[0,m),0\le a_i<n$
• $\forall i\in[0,m),0\le b_i\le\lfloor\frac{n}{2}\rfloor$
• $0\le q\le 8\times 10^5$
• $\forall i\in[1,2m-\sum_{j=0}^{m-1}[b_j=0]],0\le w_i\le 1300$
• $\forall i\in[1,q],1\le pos_i\le 2m-\sum_{j=0}^{m-1}[b_j=0]$
• $\forall i\in[1,q],0\le v_i\le 1300$ ::::: 注意到这个图上每个左部点的度最多为 $2$，所以肯定有特殊性质，这就是一个经典 trick：在两个点间连边（若一左部点只有一个度那就是一个自环）。
  但是怎么存储选择哪个点这一信息呢？注意到我们可以钦定它为有向边，那么它所指向的点就是左部点选择的点，这时每个右部点要求入度最多为 $1$，左部点的作用到此为止。
  那么这样转化有什么好处呢？
  由于保证存在完美匹配所以一个联通块的边数不能大于点数，同时由于它联通那么一个连通块要么是基环树，要么是树，现在我们分两种情况讨论：
• 基环树：
  我们贪心地想，我们不能浪费度为 $1$ 的点，这样最后就搞不出来完美匹配了，那么与它相连的边只能指向它，那么我们删去与它相连的边和它递归下去，最终会剩下一个环。
  对于一个环，我们想让它存在完美匹配那么只能全顺时针连和全逆时针连，同时维护外向边的权值和、环内顺时针边的权值和、环内逆时针边的权值和即可。
• 树：
  这时会有一个点不被选择，不妨枚举不被选择的点 $u$，最后会变成以 $u$ 为根的一棵外向树，我们随便默认一个点为根，那么对于一条边，当它是从上往下指的时候不位于下方点的子树内时会贡献答案，当它是从下往上指的时候位于下方点的子树内的时候会贡献答案，在预处理时把 DFS 序跑出来然后线段树区间修改区间求 $\max$ 即可。

然后我们就做完了这道题。
时间复杂度为 $\Theta(n+(m+q)\log n)$，空间复杂度为 $\Theta(n+m)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-19 21:14:44

:::::info[题目基本信息] 考察：莫比乌斯反演，bitset（$2500$）。
题目简介：
给定 $n$ 个可重集 $\{S_n\}$，初始均为空，有 $q$ 次操作，分为 $4$ 种：

1. 给定 $x,v$，进行操作 $S_x\leftarrow v$。
2. 给定 $x,y,z$，进行操作 $S_x\leftarrow S_y\cup S_z$。
3. 给定 $x,y,z$，进行操作 $S_x\leftarrow\{ab|a\in S_y,b\in S_z\}$。
4. 给定 $x,v$，求 $(\sum_{p\in S_x}[p=v])\bmod 2$。

数据范围：

• $1\le n\le 10^5$
• $1\le q\le 10^6$
• $1\le x,y,z\le n$
• $1\le v\le 7000$ ::::: 注意到最终求的是出现次数 $\bmod\ 2$ 的值，值域又只有 $7000$，所以我们可以考虑使用 bitset 维护每一个可重集，这样全都变成了普通集合（仍设为 $\{S_n\}$），最后的结果就是一个数是否普通集合中出现，这样操作 1,2,4 都好维护，但操作 3 不好维护。
  这时我们将操作 3 暴力计算的式子列出来观察推导一波（设 $a_{x,v}$ 为 $S_x$ 中 $v$ 的是否出现，出现为 $1$，未出现为 $0$）：
  $$\begin{aligned}a_{x,v}&=(\sum_{p\in S_y}\sum_{q\in S_z}[\gcd(p,q)=v])\bmod 2\&=(\sum_p\sum_qa_{y,p}a_{z,q}[\gcd(p,q)=v])\bmod 2\&=(\sum_{v|p}\sum_{v|q}a_{y,p}a_{z,q}[\gcd(p,q)=v])\bmod 2\end{aligned}$$ 所以我们转化需要维护的东西，设 $\displaystyle b_{x,v}=(\sum_{v|i}a_{x,i})\bmod 2$，那么我们对于每个操作看看它们能否维护。

操作 1：

由题可知此时仅有 $a_{x,v}=1$，那么 $b_{x,i}=1$ 当且仅当 $i|v$，对于每个 $v$ 预处理一下直接给 bitset 赋值即可。

操作 2：

推导：
$$\begin{aligned}b_{x,v}&=(\sum_{v|i}a_{x,i})\bmod 2\&=(\sum_{v|i}(a_{y,i}+a_{z,i})\bmod 2)\bmod 2\&=((\sum_{v|i}a_{y,i})+(\sum_{v|i}a_{z,i}))\bmod 2\&=(b_{y,v}+b_{z,v})\bmod 2\end{aligned}$$ 所以在 bitset 维护的时候直接异或起来即可。

操作 3：

推导：
$$\begin{aligned}b_{x,v}&=(\sum_{v|i}a_{x,i})\bmod 2\&=(\sum_{v|i}(\sum_{i|p}\sum_{i|q}a_{y,p}a_{z,q}[\gcd(p,q)=i])\bmod 2)\bmod 2\&=(\sum_{v|p}\sum_{v|q}\sum_{v|i}[i|p\land i|q\land \gcd(p,q)=i]a_{y,p}a_{z,q})\bmod 2\&=(\sum_{v|p}\sum_{v|q}a_{y,p}a_{z,q})\bmod 2\&=b_{y,v}b_{z,v}\bmod 2\end{aligned}$$ 所以在 bitset 维护的时候直接按位与起来即可。

操作 4：

现在我们已知 $\{b_x\}$，要反推 $a_{x,v}$。
根据莫比乌斯反演：
$$a_{x,v}=(\sum_{v|i}b_x\mu(\frac{i}{v}))\bmod 2$$ :::::success[证明] 对上式做等价转化：
$$\begin{aligned}a_{x,v}&=(\sum_{v|i}b_x\mu(\frac{i}{v}))\bmod 2\&=(\sum_{v|i}(\sum_{i|j}a_{x,j})\mu(\frac{i}{v}))\bmod 2\&=(\sum_{v|j}a_{x,j}\sum_{v|i,i|j}\mu(\frac{i}{v}))\bmod 2\&=(\sum_{v|j}a_{x,j}\sum_{i|\frac{v}{j}}\mu(i))\bmod 2\end{aligned}$$ 现在只需要证明（莫比乌斯反演）：
$$\sum_{i|n}\mu(i)=[n=1]$$ ::::success[莫比乌斯反演证明] 设 $\displaystyle n=\prod_{i=1}^mp_i^{k_i}$（即 $n$ 的唯一分解形式），那么我们得到上式中 $\mu(i)\ne 0$ 的条件是 $i|\displaystyle\prod_{i=1}^mp_i^{\min(1,k_i)}$，这个容易分析，那么 $i$ 都可以表示成若干个不同质数的乘积 $S=\displaystyle\bigcup_{i=1}^m\{p_i\}$，那么上式转化为：
$$\sum_{T\subseteq S}(-1)^T=[S=\arnothing]$$ 这个容易证明，只需简单推导：
$$\begin{aligned}\sum_{T\subseteq S}(-1)^T&=\sum_{len=0}^{|S|}(-1)^{len}\binom{|S|}{len}\&=(-1+1)^{|S|}\&=[len=0]\&=[S=\arnothing]\end{aligned}$$ :::: ::::: 不妨设 $\displaystyle g_{i,j}=\begin{cases}\mu(\frac{j}{i})\bmod 2&i|j\&\text{otherwise}\end{cases}$，那么上式可以改写为：
$$a_{x,v}=(\sum_ib_xg_{v,i})\bmod 2$$ 这个直接预处理 $g$ 然后在询问时将 $b_x$ 和 $g_v$ 两个 bitset 按位与后调用 count 函数即可。

时间复杂度为 $\Theta(V\ln V+\dfrac{qV}{w})$（由于我实现的不太好所以实际是 $\Theta(V^2+\dfrac{qV}{w})$ 的），空间复杂度为 $\Theta(V+\dfrac{V^2+nV}{w})$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-20 21:15:05

:::::info[闲话] 尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。 ::::: :::::info[题目基本信息] 考察：STL，整体转移（省选/NOI-）。
题目简介：
有 $n$ 条直线和 $m$ 个桥，第 $i$ 个桥连接了 $(t_i,d_i)$ 和 $(t_i\bmod n+1,d_i)$，初始时你在 $(k,0)$，你可以不花费任何代价地向右行走任意实数长度，直到你的位置是一座桥的端点，这时你必须沿着桥走到另一端，但是在一开始的时候你可以花费 $1$ 的代价任意钦定 $t$ 和 $d$ 建一座桥（$t\in[1,n]$，同时 $d$ 可为任意实数），问最终抵达 $(s,+\infty)$ 最小代价，你需要对于每一个 $k$ 满足 $k\in[1,n]$ 求解答案。
数据范围：

• $3\le n\le 2\times 10^5$
• $1\le s\le n$
• $0\le m\le 5\times 10^5$
• $\forall i\in[1,m],1\le d_i\le 10^9,1\le t_i\le n$
• $\forall i,j\in[1,m],i\ne j,d_i\ne d_j$ ::::: 首先 $n$ 个起点 $1$ 个终点看起来就很怪，我们把移动的过程倒过来变成 $1$ 个起点 $n$ 个终点看起来就很对了。
  存在 $\Theta(nm)$ 的 01bfs 的暴力做法，但是对正解没有启发性，但是存在有启发性的 DP 做法。
  将桥按 $d_i$ 降序排序，设 $f_{i,j}$ 为考虑完前 $i$ 个桥后位置 $j$ 的答案，初始时 $\forall i\in[1,n],f_{0,i}=\min(|s-i|,n-|s-i|)$，考虑如何转移。
  看图（为方便画图我们断环为链的画）：
  
  这时我们要在 $G$ 点和 $H$ 点间建一座桥，首先先交换这两点的答案，然后：
  注意到 $H$ 点和 $I$ 点间差距大于等于 $2$ 了，我们可以从 $I$ 点建桥到达 $H$ 点，这样答案会更小，那么我们就有了思路：
• 先交换两个建桥位置的答案。
• 再对这个序列更新减小答案，具体地，找到这个序列最小值然后向两侧更新，不断递归这个过程即可。

复杂度不重要，重要的是思想。
注意到两个相邻的数之间只能相差 $-1,0$ 或 $1$，但是然后怎么办？
然后我们看刚刚的那两步：

• 交换建桥位置的答案，这个容易直接跑，接下来会产生相差的值不为 $-1,0,1$ 的相邻数对，怎么办？
• 我们不妨以交换的位置的差分类讨论，当两数相等时交换没有影响，现在只剩后面的数比前面的数大 $1$ 或小 $1$ 的情况，这两种情况类似，可以互相轴对称得出，不妨以后面的数比前面的数大 $1$ 讨论。
  如图，黑线是原来的答案构成的序列，红线是交换 $B$ 点和 $C$ 点后的答案序列，后面这一段被连续的拉下来一段（因为一直存在相差值超过 $1$ 的相邻数对，直到 $H$ 点）注意到中间这一段相邻数对前后都相差 $1$，所以我们可以考虑维护差分序列，同时维护序列中不为 $1$ 的位置序列，这个可以使用 set 维护，更新差分序列时同时更新 set 即可。
  至于细节处理仔细分讨一下也能推出（但是一坨），需要根据建桥的两个位置以及后方第一个不是 $1$ 的位置（或前方第一个不是 $-1$ 的位置）分类讨论，讨论不清楚的话细节见代码。

这样我们就做完了这道题。

时间复杂度为 $\Theta(n+m\log n)$，空间复杂度为 $\Theta(n+m)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-21 10:48:57

:::::info[闲话] ::::: :::::info[题目基本信息] 考察：基环树，组合数学，Ad-hoc（$2800$）。
题目简介：
给定序列 $\{a_n\}$，你可以进行若干次下面的操作：

• 选择一个 $i\in[1,n]$，交换 $a_i$ 和 $a_{a_i}$。

问最终能得到的序列个数对 $10^9+7$ 取模的结果。
数据范围：

• $1\le n\le 10^6$
• $\forall i\in[1,n],1\le a_i\le n$ ::::: 闲话里已经透露了，套用经典建图 trick，我们可以建图连边，连出 $i\rightarrow a_i$ 的一条边，形成了一个 $n$ 个点 $n$ 条边的内向基环树森林。
  我们考虑观察操作前后图的变化，原来的图有 $i\rightarrow a_i\rightarrow a_{a_i}$，现在操作后交换了 $a_i$ 和 $a_{a_i}$（下文简称操作 $a_i$），那么变成了 $i\rightarrow a_{a_i}$ 以及 $a_i\rightarrow a_i$。
  我们观察到若一个点连成了一个自环，那么再次操作它会无效，我们为方便最后的计数钦定不能再操作这个点。
  但是我们观察到图的改变会对我们的计数带来很大的麻烦，所以我们不妨不改变图的形态，只给 $i\rightarrow a_i$ 这条边打一个标记，那么通过标记我们能否还原最终的 $\{a_n\}$ 序列？
  答案是肯定的：
• 若点 $u$ 存在一条入边被打标记，那么点 $u$ 已经被操作过，$a_u=u$。
• 否则，我们从点 $u$ 开始，不断走它的出边，直到找到一条没有被打标记的边，它的出点 $v$ 就是 $a_u$。

容易发现每个合法标记序列能够唯一映射到一个 $\{a_n\}$ 序列，由于每个点最多有一条入边被打标记那么答案上界就是 $\displaystyle\prod_{i=1}^nind_i+1$，其中 $ind_i$ 是 $i$ 点的入度。
那么这是否就是答案？
这并不是。
举个例子，一个环上的边全部标记就不合法，因为你在打最后一条边的标记时 $a_u$ 已经全部等于 $u$，无法再操作，也就是说一个环上只有一条边未被操作时不能再对环上的点进行操作了，那么枚举环上的点 $u$，操作 $u$ 的可能性有 $ind_u$ 种，那么可能就会有 $\displaystyle\sum_{u}ind_u$ 种不合法的标记序列了。
那么最终我们就得到了答案的式子：
$$(\prod_{cycle\in\text{cycles}}(\prod_{u\in cycle}ind_u+1)-(\sum_{u\in cycle}ind_u))\cdot(\prod_{u\notin\text{cycles}}ind_u+1)$$ 这样我们就做完了这道题。
时空复杂度均为 $\Theta(n)$。

code