本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-03-09 01:24:05
省选已经结束了，但是感觉梦熊模拟赛好题不少，所以文化课开课之前把题解补了下。
D1T1 删点 MST
题意
给定 $n$ 点 $m$ 边的无向连通图，对每个点求删掉该点及所连接的边后剩余图的最小生成树，不连通输出 $-1$。$n,m\le 5\times 10^5$。
题解
先跑出原图的最小生成树，那么删点后没被删掉的树边保留一定不劣，那么需要用非树边将 $d_x$ 个连通块连起来，其中 $d_x$ 表示所删掉点在树上的度数。
注意到一条非树边 $(u,v,w)$ 只会在 $(u,v)$ 树上路径上的点被删时才有可能被选，又注意到若被删的点不是 $LCA(u,v)$，则两点中必有一点是所删点的父亲连通块中的。所以路径上除 $LCA(u,v)$ 和与 $LCA(u,v)$ 相邻的点以外的点 $x$ 在父亲 $fa_x$被删掉时，都会存在一条权为 $w$，连接 $x$ 和 $fa_{fa_x}$ 连通块的边。注意到这种边除边权以外没有区别，所以拆成两次链取最小值即可，这样就维护出了每个点这样的最小边权。
另外对于 $LCA(u,v)$，其被删除时包含 $u$ 和包含 $v$ 的子树之间存在一条权为 $w$ 的边，因为 LCA 唯一，直接记录即可。对每个点求解时取出所有子节点向父亲的最小连边和记录的所有边，跑一遍 Kruskal 即可。这样点数总和是 $\sum d_i = O(n)$ 的，边数总和是 $O(n+m)$ 的，复杂度瓶颈为树剖的 $O(m\log^2 n)$。
D1T2 毒药
题意
给定一棵树，点有点权 $a_i$，求满足 $a_x\oplus a_y\le \bigoplus_{i\in Path(x,y)} a_i$ 的二元组 $(x,y)$ 个数。$n\le2\times 10^5,a_i\le 2^{60}$。
题解
记 $d_i$ 表示 $i$ 到根的路径异或和，则原条件转化为 $a_x\oplus a_y\le d_x\oplus d_y\oplus a_{LCA(x,y)}$。则容易想到枚举 LCA，统计不同子树之间点对的贡献。然而这样遍历的总次数没有保证，所以使用点分治，上式中 $d$ 也变成点到分治中心的路径异或和。则问题转化为动态维护集合 $S$，集合元素为 $(a,d)$ 二元组，多次询问 $(a_x,d_x)$，查询集合 $S$ 中有多少 $(a_y,d_y)$ 满足 $a_x\oplus a_y\le d_x\oplus d_y\oplus a_{rt}$。
发现只有令含 $x$ 项和含 $y$ 项分别在同侧，才能快速维护数量。但小于号没有交换律，所以先变不等号并移项，得到 $a_x\oplus d_x\oplus a_{rt}\ne a_y\oplus d_y$，然后按照 $a\oplus d$ 分类后枚举 LCP 长度，分讨不同的最高位，最后加上相等的贡献即可。实现只需开一棵以 $a\oplus d$ 为键值的 Trie 树，每个点记录子树内 $a$ 该位为 $0$ 或 $1$ 的个数，可通过 $a\oplus d$ 的情况得到 $d$ 该位的值。查询时从根到对应叶子遍历一条链，处理链上节点的兄弟节点即可。
原题
点分治后的部分：P7502。
D2T1 跳跃树桩
题意
给出 $n$ 个树桩，每个树桩有位置 $x_i$ 和价值 $a_i$，从第一个树桩跳到第 $n$ 个，要求在 $x$ 时只能跳到 $[x+L,x+R]$ 内的树桩，求最终经过树桩的价值降序排序后最大的字典序。$n,a_i\le 5\times 10^5,x,L,R\le 10^9$。
题解
考虑如果直接 DP，有 $f_{i}=\max_{x_i-R\le x_j\le x_i-L} f_j + a_i$，这里对 $j$ 的限制显然可以单调队列优化，但是 max 是比较字典序，$a_i$ 也需要插入正确位置，直接暴力插入和比较是 $O(n^2)$ 的，无法通过。
发现如果在桶上记录每个数在序列中出现的次数，插入时变化的位置只有一个，比较时从大到小找到第一个数量不同的位置，较多的即为字典序较大的。使用可持久化线段树维护桶的哈希值，从而用线段树二分实现比较，单点修改即可。时空复杂度 $O(n\log n)$。
D2T2 清除敌人
题意
给定 $n$ 个点 $m$ 条边的有向无环图，起点为 $1$ 号点。可以沿着有向边移动，也可以在任意时刻直接返回 $1$ 号点。到达一个存在敌人的点时，需要消耗 $a_i$ 点血量清除，清除后恢复 $b_i$ 点血量，但整个过程中血量都不能低于 $0$。问最少需要多少初始血量才能清除所有敌人。$n+m\le72,a_i,b_i\le 10^{15}$。
题解
考虑如果没有任何顺序限制怎么做，此时若存在 $i,j$ 两个点，则先取 $i$ 需要的血量下限为 $\max(a_i,a_i-b_i+a_j)$，先取 $j$ 需要的血量下限为 $\max(a_j,a_j-b_j+a_i)$，注意到这样可以确定任意两个之间的顺序，且比较有传递性，所以按照这样的顺序清除即可。
那么把这个放到树上怎么做？考虑排序后第一个点，那么一旦其父亲被清除，其一定会被马上清除，所以可以将其与父亲合并为一个点，新值为 $a'=\max(a_f,a_f-b_f+a_x),b'=b_f-a_f+b_x-a_x+a'$，这样和原来的两个点先后清除等价。原先两个点的所有儿子都接在这个新点上，直到最后只剩一个节点时其 $a$ 值即为答案。
那 DAG 怎么做？注意到 $n+m$ 很小，所以 $n$ 比较小时直接 $O(2^nn)$ 状压 DP 解决，大概能做 $n\le24$。那么剩余情况下 $m\le48$，这时搜索出所有可能的外向树，对每种树做一遍刚才树上的做法，复杂度为 $O(cn\log n)$，其中 $c$ 为外向树方案数。考虑计算方案数的上界，此时 $n\ge 24,\sum d_i=m\le 48,c=\prod d_i$，其中 $d$ 为某个点的入度。根据均值不等式，所有 $d$ 均相等时 $c$ 最大，也即 $(\frac mn)^n$，在最大的 $n=24,m=48$ 时即为 $2^{24}$，总复杂度为 $O(2^{\frac {n+m}3}n\log n)$。
D2T3 括号序列
题意
给定 $n,m,k,mod$，求在 $n$ 个盒子中各放一个长度不为 $2k$ 的合法括号序列，总长为 $2m$ 的方案数，对 $mod$ 取模。$n,m,k\le 10^7$。
原题 + 题解
数据弱化版：AT_kupc2020_m，题解。
D3T1 简单函数
题意
给定 $n$ 个数 $x_i$，需要支持单点修改，询问 $i\in[1,n)$ 中是否存在 $i$ 满足 $f(x_i)f(x_{i+1})\le 0$，其中 $f(x)=(a\oplus x)-b$，每次询问给出 $a,b$。若存在则输出任意一个，否则输出 $-1$。$n,q\le 10^6,x,a,b<2^{30}$。
题解
考虑如果 $\max (a\oplus x)<b$ 或者 $\min(a\oplus x)>b$，则所有的 $f(x)$ 均同号，无解。否则 min 和 max 的 $f$ 值异号，考虑先找到这两个位置 $l,r(l<r)$，我们已知它们异号，则可以找到 $mid=\frac{l+r}2$，此时 $l,r$ 中一定存在与 $mid$ 异号的，所以判断一下即可把区间缩短到原来的一半，$O(\log n)$ 次即可将区间缩小到 $[i,i+1]$，输出即可。
实现上需要求出 $(a\oplus x)$ 的最值及其位置，所以对所有 $x$ 建 Trie 树，在叶子节点上记录对应的所有下标即可，可以使用 set 或可删堆，也可以在外面单开一个 set 记录值和下标的对应关系。时间复杂度 $O(q(\log V+\log n))$。
D3T2 异或大师
题意
给定长为 $n$ 的序列 $a$，可以任意次将 $a_i$ 赋成 $a_i\oplus a_{i-1}$，求操作后的最长上升子序列长度。$n\le 3\times 10^5,a_i\le 10^9$。
题解
注意到 $a_i$ 可以任意异或 $i$ 前面的所有数，也即可以在 $i$ 前面选出任意一个子集异或给 $i$，线性基就可以很好地表示出任选子集的异或值。
考虑直接设 $f_i$ 表示目前长为 $i$ 的上升子序列的最小结尾，暴力转移的话每次枚举所有的 $f_j$，找到线性基中所有数异或 $a_i$ 得到的大于 $f_j$ 的最小值，用这个值更新 $f_{j+1}$，复杂度 $O(n^2\log V)$。
又注意到线性基只会变化最多 $\log V$ 次，那么若在 $a_p$ 处改变，直接使用 $a_p$ 暴力转移，后面下一次改变之前的所有数取值方式均相同，考虑整体转移。假设相同的位数为 $d$，则先找到线性基中大于 $f_j$ 的最小值，求出其在线性基中的从小到大的排名 $k_j$。那么 $f_j$ 后面最多可以加上 $\min(siz-k_j+1,d)$ 个数，$siz$ 为线性基能表示的数的个数。
那么若由 $f_j$ 转移到 $g_i$，则 $g_i$ 的值为线性基中第 $(k_j+i-j-1)$ 小的数，由于 $f_j$ 能转移的 $i$ 有上界，用单调队列维护目前可以用来转移的 $j$，$k_j-j$ 较小的较优，转移时在线性基中求第 $k$ 小即可，单轮转移复杂度为 $O(n\log V)$，总时间复杂度为 $O(n\log^2V)$，有一些边界情况需要特殊处理。
D4T1 爬山
题意
有长为 $n$ 的山，每处有高度 $a_i$，初始 $a$ 不降。当处在第 $i$ 个位置时，可以将 $a_i$ 增加 $1$ 或将 $a_{i+1}$ 减少 $1$，只有在 $a_{i}=a_{i+1}$ 时才能从 $i$ 走到 $i+1$。现要连续爬 $k$ 次山，每次从 $1$ 开始走到 $n$，高度的变化会保留，求总共需要增加或减少的最少次数。$n,k\le2\times 10^5,a_i\le 10^9$。
题解
发现一定可以从某个位置将整个序列分成两半，其中前半部分每次走时只通过增高自身通向下一格，后半部分在第一次爬山中推平成相等，之后均直接走过去。设分界点为 $x$，则推平后半部分的代价为 $\sum_{i=x+1}^n a_i-a_x$，现在还要计算每个前缀在 $k$ 次爬山中的总贡献。
注意到这个前缀每次是整体左移一格，并把结尾复制了一份放在结尾。所以考虑一个 $a_i<a_{i+1}$ 的位置 $i$，在前 $i$ 次爬山时均存在这样的间隔，需要增高 $(a_{i+1}-a_i)$ 次以通过，之后该间隔就被右移没了。所以贡献为 $(a_{i+1}-a_i)\times \min(k,i)$，记录前缀贡献，与后缀代价拼起来取最小值即可。复杂度 $O(n)$。
D4T2 生成树
题意
给定 $K,V,E$，要求构造一张点数不超过 $V$，边数不超过 $E$ 的有向图，使得其中存在节点 $r$ 使得以 $r$ 为根的外向生成树个数恰好为 $K$。$V=80,E=220,K\le 10^{18}$。
题解
考虑把 $K$ 的二进制位拆出来分别构造。先连一条长为 $(\log K+1)$ 的有向链，以链头为 $r$。另开一个点 $T$，向链上所有除 $r$ 以外的点连有向边。此时从链尾向 $r$ 从 $0$ 开始标号，标号为 $i$ 的点只要向 $T$ 连一条有向边，就会对方案数产生 $2^i$ 的贡献。
由于可以用这样的边连接上 $T$，同时这些边只会选一条，所以相互独立。选择第 $x$ 条边后，所有 $i<x$ 的 $i$ 均可以从 $T$ 或 $(i+1)$ 连过来，贡献为 $2^i$。这样总点数为 $\log K +2$，总边数不超过 $3\log K$，符合题目要求。
D5T1 抽卡
题意
给定 $n\times m$ 的网格，其中有一些格子是关键格。每轮等概率选中一条两个格子之间的边，覆盖对应的两个格子，求期望多少轮能覆盖所有的关键格。$n\le 7,m\le 200$。
题解
我们发现要求的是 $\max_{x\in S} t_x$ 的期望值，其中 $t_x$ 表示 $x$ 被覆盖的时间。发现这个 max 很不好算，但如果是 min 的话，找出所有关键点周围的所有边，期望即为选中这些边之一的期望次数，每轮选中的概率为 $\frac {cnt_S}{sum}$，期望次数即为倒数 $\frac{sum}{cnt_S}$。那么通过 min-max 容斥即可得到 $\max_{x\in S} t_x=\sum_{T\subseteq S}(-1)^{\left|T\right|+1}\frac{sum}{cnt_T}$。
现在需要快速统计右面的值，也就是需要求出每种 $cnt_T$ 的点集选择方案的容斥系数之和。考虑轮廓线 DP，设 $f_{i,j,S,c}$ 表示考虑到 $(i,j)$ 格子，$S$ 中的所有为 $1$ 的行左边已选，在两边的格子都已经考虑过的边中有 $c$ 条边能覆盖到，这样的点集容斥系数之和。转移时枚举当前点是否选，多考虑上两条边并更新 $c$ 即可。最终对所有不同的 $c$ 用容斥系数统计答案，DP 状态数 $O(n^2m^22^n)$，转移 $O(1)$，总复杂度 $O(n^2m^22^n)$。
原题
数据弱化版：UOJ422。
D5T2 分裂
题意
有一个 $4$ 行无穷列网格，初始只有一只生物在 $(0,0)$ 处。每次可以任选一只生物，使其消失并在 $(x,y+1)$ 和 $((x+1)\bmod 4,y+1)$ 处分别产生一只新生物，需要保证这两个格子里原来是空的。对于所有 $i\in[1,n]$，求分裂 $i$ 次后生物分布状态的方案数，对输入的模数取模。$n\le 10^6$。
题解
注意到如果有一个位置出现过 $4$ 次生物，或者同一列总共出现过 $8$ 个生物，那么后面一定会无限复制下去，一定不能满足题意。所以用四个值 $S=(a_0,a_1,a_2,a_3)$ 表示该列第 $i$ 行出现过 $a_i$ 次生物，然后 $2^4$ 枚举最终这一列是否保留，把剩下的推到后一行，这样就可以得到下一行各点被经过的次数 $T$，可以连一条从 $S$ 到 $T$，边权为该列操作次数的边。
如果把所有状态看做点，带权的转移看做边，那么 $i$ 的答案即为起点 $(1,0,0,0)$，终点 $(0,0,0,0)$ 且长为 $i$ 的路径数量。搜索可得从起点能到达的状态只有 $26$ 个，直接设 $f_{i,j}$ 表示从起点到第 $j$ 个状态长为 $i$ 的路径条数，暴力转移即可。时间复杂度为带常数 $26$ 的 $O(n)$。
D6T1 串
题意
给定两个长为 $n$ 的串 $S,T$，现选出一些位置，在两个串中同时将这些位置的字符删去，把剩下的字符拼接成 $S',T'$，求字典序最大的 $S'+T'$。$n\le 47$。
题解
考虑直接设 $f_i$ 表示目前保留 $i$ 个位置时字典序最大的 $S'+T'$，每次枚举所有 $f_i$ 并尝试转移给 $f_{i+1}$。注意比较大小时由于长度相同，可以直接比较，为了插入方便也可以开两个串分别记录 $S',T'$，依次比较即可。最后在所有 $f$ 中取字典序最大的即为答案，时间复杂度 $O(n^3)$。
D6T2 环
题意
有 $N=2A+B$ 根绳子，其中两端红和两端绿的绳子各有 $A$ 根，一端红一端绿的绳子有 $B$ 根，将所有红端点和绿端点随机匹配，即在 $N!$ 种方案中随机选择一种，把匹配的端点连接起来形成若干个环，求环个数的期望。$A,B\le10^6$。
题解
若 $B>0$，则取出一根红绿绳子，分讨其红色端点的连接情况：
- 连接自己的绿色端点，环数增加 $1$。
- 连接其他红绿绳子的绿色端点，环数不变，合成一根新的红绿绳子。
- 连接绿绿绳子的某个端点，环数不变，合成一根新的绿绿绳子。
注意到三种操作都使得红绿绳子的数量减少了 $1$，其余不变，且只有第一种向答案贡献了 $1$。因此当 $B>0$ 时，可将答案增加 $\frac 1{2A+B}$，之后 $B$ 减少 $1$。这一部分贡献为 $\sum_{i=1}^B \frac 1{2A+i}$。
之后 $B=0$，则再取出一根红红绳子，其一个端点一定连接着某根绿绿绳子，所以把这两根绳子合成一根新的红绿绳子，也即 $A$ 减少 $1$，$B$ 增加 $1$，接着计算贡献直到 $A,B$ 均为 $0$ 即可，这部分贡献为 $\sum_{i=1}^A\frac 1{2i-1}$。两部分贡献加起来即为答案，时间复杂度 $O(A+B)$。
D6T3 树
题意
给定一棵树，点有点权，$q$ 次询问 $(x,k)$，找出 $x$ 子树内所有距离 $x$ 不超过 $k$ 的点，求这些点点权与其到 $x$ 距离的异或值的和。$n,q\le 10^6,a_i\le 10^9$。
原题 + 题解
P10107，题解。
D7T1 染色游戏
题意
有 $n\times n$ 的网格，初始全为白色。每次操作会把一整行全部覆盖成红色，或是把一整列全部覆盖成蓝色。已知每行每列都恰好被操作过一次，给出最终网格中每个格子的颜色，求有多少种操作方案可以得到这样的网格。$n\le 2000$。
题解
注意到每个格子只会被覆盖两次，且被行操作时会变成红色，被列操作时会变成蓝色，因此 $(i,j)$ 的最终状态就限制了第 $i$ 行和第 $j$ 列的操作顺序。把每行每列都建成一个点，每个格子的限制连成一条有向边，操作方案数即为这张图拓扑序的数量。
但是拓扑序计数做不了，注意到如果忽略边的方向，这是一张完全二分图。这也意味着两部分不可能同时存在没有入度的点。所以每次取出没有入度的一组点，它们的先后顺序任意，将答案乘上个数的阶乘并且全部删除，继续拓扑即可。时间复杂度 $O(n^2)$。
D7T2 01 序列
题意
给出一个长为 $n$，某些位置不确定的 $01$ 序列，不确定的位置在 $01$ 中等概率选择。设一个 $01$ 序列的权值为 $a\times b$，其中 $a$ 为最长不下降子序列长度，$b$ 为最长不下降子序列中 $1$ 的最大个数，求该序列权值的期望。$n\le 1000$。
题解
考虑一个 $01$ 序列如何求其权值，一定是找到一个分界点 $p$，选择其前面的所有 $0$ 和后面的所有 $1$，并且在保证长度最大的前提下使得 $1$ 的数量尽可能多。如果把 $0$ 看作 $-1$，再对原序列求前缀和后放到坐标系中，得到一张折线图。注意到取最低点为分界点时子序列一定最长，因为非最低点移动至最低过程中答案会增加。为了同时让 $1$ 最多，应该选择最靠左的最低点为分界点。
那么考虑记 $f_{i,j}$ 表示考虑了前 $i$ 个字符，目前纵坐标比前缀最低点高 $j$ 个单位的答案。但是这样转移很困难，所以考虑记录 $1,a,b,ab$ 四个值目前的和，其中 $1$ 即为到这个点的方案数。当加入 $1$ 时从 $f_{i-1,j}$ 转移到 $f_{i,j+1}$，其中 $a,b$ 均加了 $1$。加入 $0$ 时分有没有产生新的最低点讨论，若不产生则没有任何贡献，直接把 $f_{i-1,j}$ 累加给 $f_{i,j-1}$ 。若产生则只更新 $1$ 和 $a$，$b,ab$ 均变成 $0$ 所以不转移。这里 $a$ 还要增加 $1$，原因的话考虑从上个最低点到 $(i-1)$ 的 $01$ 个数相同，在状态的 $a$ 内统计了 $1$ 的贡献，只需要再加上最后一个 $0$ 即可。
最后统计所有 $f_{n,i}$ 的 $ab$ 的和，除以总方案数 $2^{cnt}$ 即为答案。时间复杂度 $O(n^2)$。
D7T3 区间
题意
给出一个长为 $n$ 的序列 $a$，对于 $x\in[1,k]$ 求有多少个区间 $[l,r]$ 满足 $\gcd(\max_{i=l}^ra_i,\min_{i=l}^ra_i)=x$。$n,k,a_i\le 2\times 10^5$。
题解
由于是最大值和最小值的关系，考虑单调栈或分治。这题可以单调栈 + 线段树做，但是分治做法更好想，常数也比较小。
考虑从 $[1,n]$ 开始分治，每次只统计跨过 $mid$ 的区间答案，然后分治到两边继续统计。分讨最大值位置，若最小值在同侧，则另一侧的长度有上界，直接将答案 $r$ 累加上长度个数即可。若最小值在异侧，则另一侧的长度由于最大值在另一侧有上界，由于最小值在该侧有下界。这时枚举最大值侧的长度，相当于要在另一侧维护一个可重集 $S$，支持动态增删点，同时给出 $x$ 后可以对于所有 $y\in S$，给 $c_{\gcd(x,y)}$ 加上 $1$。
考虑设 $c'x$ 表示 $x$ 为公因数出现了多少次，此时不一定是最小公因数，那么 $c_x=c'_x-\sum{y\mid x,y>x} c'_y$，维护 $c'$ 即可。考虑记数组 $t_d$ 表示目前 $S$ 中 $d$ 的倍数个数，插入或删除时枚举因数更新 $t$，查询时枚举所有 $x$ 的因数 $ d$ 给 $c'_d$ 加上 $t_d$ 即可。最后反演出 $c$ 后累加给 $r$ 即为答案。时间复杂度 $O(nd(n)\log n)$。
2.13T2 神庙
题意
给出一个排列 $p$，每个位置可以选择加上 $10^{100}$ 或不变，之后通过邻项交换使其变为升序，求加完后需要交换的最少次数。$n\le 2\times 10^5$。
原题 + 题解
需要转化的数据弱化版：AT_awtf2024_d，题解。
2.14T2 数位
题意
给出一个某些位不确定的 $01$ 串，填满后按顺序使用 $a_i$ 对 $x$ 进行操作，初始 $x=0$。操作为若 $a_i=0$，则 $x=x-f(x)$，否则 $x=x+f(2^k-1-x)$，其中 $f(x)$ 表示 $x$ 的 lowbit 值，$f(0)=0$。对所有 $i\in [1,n]$ 的 $i$，求有多少种填 $01$ 的方案使得 $s_i=0$，且最终 $x\le r$。$n\le 10^5,k\le 20$。
题解
首先考虑一个显然的暴力，设 $f_{i,j}$ 表示进行完前 $i$ 个操作后 $x=j$ 的方案数，可以直接转移。再设 $g_{i,j}$ 表示当前 $x=j$ 时，再进行 $[i,n]$ 中的所有操作后不超过 $r$ 的方案数，同样可以直接转移。对每个位置求答案时用 $f_{i-1}$ 和 $g_{i+1}$ 拼起来，中间进行一次 $a_i=0$ 的转移即可。时间复杂度为 $O(2^kn)$。
上述做法由于状态数就有 $nV$，转移也难以优化，所以考虑压缩状态数。发现可以记录 $x$ 和 $r$ 的 LCP 长度，这样通过第一个不同位即可区分大小。为了得知进行操作后的情况，还要记录 LCP 之后 $1$ 的个数，才能在操作时得知 LCP 的变化情况。据此设 $f_{i,j,k},g_{i,j,k}$ 分别表示 $x$ 与 $r$ 的 LCP 长为 $j$，LCP 之后还有 $k$ 个 $1$ 的所有 $x$ 的总方案数，其他含义与暴力相同。这里可以预处理 $to_{j,k,0/1}$ 表示转移到的 $j',k'$，此处有巨大分讨，其余做法不变，时间复杂度 $O(k^3+nk^2)$。
搬题
U535402。
2.14T3 数论
题意
设 $f(p,q,r)$ 为方程 $px\equiv q\pmod r$ 的最小非负整数解，无解则为 $0$。$T$ 次询问给定 $n,a,b$，求 $\sum_{i=1}^n f(a,b,i)$，取模输出。$T\le 5,n\le 10^{18},a,b\le 10^6$。
题解
根据题意 $f(a,b,i)$ 即为 $ax+iy=b$ 中 $x$ 的最小非负整数解，此时若 $i>\max(a,b)$，则 $y=\frac{b-ax}i \le \frac bi<1$，因此 $y<0$。所以可以设 $z=-y$，原式即 $ax-iz=b,x=\frac {b+iz}a$。此时使 $x$ 取到最小非负整数的 $z$ 需要满足 $z$ 非负且 $b+iz$ 整除 $a$，也即 $iz\equiv -b\pmod a$，根据定义得 $z=f(i,-b,a)$。
显然 $f(p,q,r)=f(p\bmod r,q,r)$，那么 $\max(a,b)$ 及以下的直接暴力，$\max(a,b)$ 以上的按对 $a$ 取模的值分类，每一类的 $z$ 相同，则为一个等差数列，计算一下左右端点累加即可。求 $f$ 直接使用扩展欧几里得，时间复杂度 $O(V\log V)$，其中 $V$ 为 $a,b$ 的值域。
原题
Gym104053F。
2.17T1 删树
题意
给定一棵 $n$ 个点的树，每次操作需要选择一部分点删去，要求操作后整棵树仍连通。对于 $k\in[1,n]$，求恰好 $k$ 次将整棵树删空的方案数。$n\le400$。
题解
考虑在固定根节点，并且要求每个点不晚于其父亲被删时求解。那么我们设 $t_u$ 表示 $u$ 点被删去的轮数，要求即为 $t_{u}\le t_{fa_u}$。这样的 $t$ 的方案数可以直接使用树形 DP + 前缀和优化求出。然而可能会出现某一轮没有节点被删的非法情况，需要容斥减去。这里设 $r'i$ 表示求出的方案数，那么 $r_i=r'_i-\sum{j=1}^{i-1} r_j\times {{i-1}\choose {j-1}}$，也即要减去实际上只有 $j$ 轮操作有点被删的方案数。
但是对于一种删除方案，所有在最后一次被删除的连通块内的点为根时均会被记录一次，为了统计最终答案，还需要进行点边容斥，也即对于每条边，将其两端点缩为一个点作为根，将其答案在最终答案中减去。这样每个连通块的点数与边数之差为 $1$，最终贡献即为 $1$，时间复杂度 $O(n^3)$。
如果要优化复杂度，考虑优化跑 $n$ 遍 $O(n^2)$ DP 的过程，也即通过换根降低复杂度。但是这个把两个点缩成一个后的 DP 难以换根，只能直接更换一种统计答案的方式。考虑钦定每个连通块中在以 $1$ 为根时深度最小的结点为代表，对于每个在最后删除的连通块只在其代表处统计答案。
这样就可以换根了，只要在换根时要求父亲删除的轮次小于该节点即可，仍然可以前缀和优化，统计答案同样容斥。另外换根时从父亲的状态中删去自身需要乘逆元，这个可以在 $O(n+\log n)$ 的复杂度内类似阶乘预处理，时间复杂度 $O(n^2)$。
搬题
数据加强版：U536130。
2.17T2 移动点集
题意
给定数轴上 $n$ 个点的位置 $x_i$，对于每个点只能将其放在 $x_i-d$ 或 $x_i+d$，放完后需要用若干个区间覆盖所有点，一个区间 $[l,r]$ 的代价为 $a+b(r-l)$。求任意放置后覆盖所有点的最小代价。$n,x_i\le 100,d\le 50$。
题解
我们把位置要求变成 $x_i$ 或 $x_i+2d$，此时若 $d$ 比较小，可以状压 DP，设 $g_{i,S,0/1}$ 表示填到 $i$ 位置，最近的 $2d$ 个位置有无点的情况为 $S$，且 $i-2d$ 位置是否被覆盖时，$i-2d$ 及之前位置总花费的最小值。讨论一下转移即可，复杂度 $O(V4^d)$，其中 $V$ 为 $x_i$ 的值域。
另外还可以注意到模 $2d$ 同余的 $x$ 可以放到一起考虑位置，那么 $d$ 比较大时，每个同余类内的点数 $\frac V{2d}$ 就比较小了。那么此时考虑直接 $2^{\frac V{2d}}$ 枚举每个等价类内的状态，然后 DP 把等价类拼接起来即可。在 $S$ 后面拼上 $T$ 时两者中均为 $1$ 的位置贡献 $\min(a,b)$，只有 $T$ 为 $1$ 的位置贡献 $a$。另外第一个等价类除第一个外要接在最后一个之后，所以再枚举一下第一个等价类的状态再转移，复杂度会高一些，大概为 $O(8^{\frac V{2d}}d)$。
第一个做法大概可以做 $d\le 8$，那么 $d>8$ 时 $\frac V{2d}\le 7$，后一种做法可以通过，总复杂度不再叙述。
2.17T3 最小生成树
题意
给定 $(n+1)$ 个点的无向图，点从 $0$ 开始编号。对于 $i\in[1,n]$ 有一条从 $0$ 到 $i$，边权为 $a_i$ 的边，另有 $m$ 条连接 $u_i,v_i$，边权 $w_i$ 的边，这种边不会连接 $0$ 点。每次操作修改 $a_p$ 为 $x$，每次操作后询问该图最小生成树的边权和。$n,m,q\le 5\times 10^5$。
题解
考虑如果 $m=n-1$ 且恰好把 $n$ 个点连成一条链，那么考虑 DP，设 $f_{i,0/1}$ 表示考虑了前 $i$ 个点，且第 $i$ 个点是否与 $0$ 点连通的最小花费，转移为 $f_{i,0}=\min(f_{i-1,0}+b_i,f_{i-1,1}),f_{i,1}=\min(f_{i-1,0}+a_i+b_i,f_{i-1,1}+\min(a_i,b_i))$，其中 $a,b$ 分别是连到 $0$ 和 $i-1$ 的代价。注意到可以使用 min+ 矩阵刻画转移，所以放到线段树上维护 min+ 矩阵即可支持单点修改。
那么如果不是链，就先跑出 $n$ 个点的最小生成森林，并且建出 Kruskal 重构森林。考虑把这东西等价转化成一条链，那么直接按照其中序遍历访问初始点的顺序建成链，$b$ 的值赋为 $id_i$ 和 $id_{i-1}$ 在重构树上 LCA 的点权，若不在同一棵树上则为正无穷，否则在中序遍历到时赋值即可。这样等价的原因是如果跑 Kruskal，那么在目前访问到的边权上界相同时，新图和原图中所有点对之间的连通性相同，所以在这种含义下等价。那么就转化成了一条链的情况，时间复杂度为带矩阵乘法常数的 $O(n\log n)$。
原题
Gym102962E。
2.19T1 序列
题意
给定长为 $n$ 的序列，$q$ 次询问，每次给出 $w$ 的初始值，之后依次遍历 $i\in [1,n]$，若 $w\le a_i$ 可以选择给 $w$ 异或上 $a_i$，求能异或上的数的最大个数。$n\le2\times 10^5,q\le 10^6,a_i,w< 2^{30}$。
题解
考虑找到 $w$ 的最高位，那么其一定能异或掉所有最高位低于其的数，同时与其最高位相同的数最多只能异或一个。所以答案为 $cnt$ 或 $cnt+1$，只需要对每个 $w$ 判断是否存在与其最高位相同的 $a_i$ 满足到 $i$ 时 $w\le a_i$，且异或上 $a_i$ 后还能把后面最高位低于 $w$ 的数全都异或上。
容易想到先根据 $w$ 的最高位分类，每一类分别判断。这时取出所有最高位低于 $w$ 的 $a_i$，对其求前缀异或和 $s_i$，那么若有最高位与 $w$ 相同的数 $a_x$，则满足 $w\oplus s_{x-1}\ge a_x$，且对于任意 $j>x$ 都有 $w\oplus a_x\oplus s_{j-1}\ge a_j$ 时 $w$ 便存在对应的 $a_x$，可以让答案加 $1$。
观察发现后面的 $O(n)$ 个限制有效的不多，因为从后往前非后缀最大值的限制一定可以删去，现在需要考虑相等情况。发现若存在 $p,q$ 使得 $a_p,a_q$ 均为后缀最大值，则 $w$ 异或完 $p$ 之前的元素后还需要异或上至少两个最高位与 $a_p$ 相同的，此时若 $w$ 高于 $a_p$ 则后面一定都能取完，否则异或 $a_p$ 后最高位下降，一定取不完。因此若出现两个相等的，直接将这两个限制保留并忽略之后的限制即可，这样总限制数为 $O(\log V)$ 级别。
注意到每个限制均形如 $w\oplus x\ge y$，而枚举 LCP 长度即可证明满足限制的 $w$ 在 Trie 树上为根深度不同的 $\log V$ 棵子树，那么 $O(\log V)$ 组 $\log V$ 棵子树的交形成了 $O(\log^2V)$ 棵子树，初始建出 $w$ 的 Trie 树并在上面打标记即可，时间复杂度 $O(n\log^2V)$ 或 $O(n\log^3V)$。
2.19T2 散步
题意
给定 $n$ 个二元组 $(a_i,b_i)$，定义长为 $n$ 的排列 $p$ 权值为最小的 $i\in [1,n]$ 使得 $\forall j\ge i,\sum_{k=i}^j(a_{p_k}-b_{p_k})\ge0$，且 $\forall j<i,\sum_{k=i}^n(a_{p_k}-b_{p_k})+\sum_{k=1}^j(a_{p_k}-b_{p_k})\ge 0$，若不存在则权值为 $0$。求所有 $n!$ 种排列的权值之和。$n\le 20$。
题解
注意到 $(a_i,b_i)$ 其实只会用到 $s_i=a_i-b_i$，题意中的限制其实相当于循环位移后的所有前缀和非负。此时若把 $s_i$ 的前缀和放到坐标系中，则 $i$ 对应的位置其实是最靠左的最低点。因为只有以最低点位移后的前缀和均非负，其中最小的 $i$ 即为最靠左的。那么从最低点向左即为一段始终为正的折线，向右即为一段始终非负的折线。
所以需要求出 $f_S,g_S$ 分别表示使用 $S$ 中的 $s_i$ 拼成始终为正或非负的折线方案数，枚举下一个选的段，判断合法并转移即可。这里需要注意 $f$ 是反着向左始终为正，也即 $s$ 的和始终为负。若设 $U$为全集，答案即为 $\sum_S f_S\times g_{U-S}\times{\left|S\right|}$。时间复杂度 $O(n2^n)$。
2.21T1 异或树
题意
给定一棵 $n$ 个点的树，点有点权，分别求树上点两两之间路径按位与、按位或、按位异或值平方的和。$n\le10^5,a_i< 2^{25}$。
题解
由于都是位运算，考虑拆位计算贡献。一个数可以表示为 $\sum_{k=1}^x 2^{p_k}$，其平方即为 $\sum_{k=1}^x\sum_{l=1}^x 2^{p_k+p_l}$，因此枚举 $p_k,p_l$，求有多少条路径的值中 $p_k,p_l$ 两位均为 $1$，累加贡献即可。只需要设 $f_{u,0/1,0/1}$ 表示从 $u$ 点向其子树内的链中，$p_k,p_l$ 两位分别为 $0/1,0/1$ 的链数量，直接转移并在 LCA 处统计贡献即可。
可以加一些常数优化，重要的是只跑 $p_k\le p_l$ 的部分，将 $p_k<p_l$ 的贡献翻倍即可。不太重要的还有计算与和或答案时可以少开一些之类，但是不加也能过。时间复杂度为 $O(n\log^2 V)$，带着不小的常数。
原题
QOJ5566。
2.21T2 矩阵填数
题意
有一个 $n\times n$ 的矩阵，给出 $n$ 个限制 $(x,y,c)$，向矩阵内填数，要求 $a_{i,j}\ge a_{i,j+1}$ 且 $a_{i,j}\ge a_{i+1,j}$，求满足该要求的前提下 $\sum_{i=1}^n \left|a_{x_i,y_i}-c_i\right|$ 的最小值。$n\le 2\times 10^5$。
题解
显然若一个位置填的数不为某个 $c$，一定可以调整到 $c$ 且答案不增，因此先对 $c$ 离散化即可。考虑若 $c\in\{0,1\}$，那么 $1$ 和 $0$ 之间的分界线一定是一条从右上到左下的折线。考虑对这条线 DP，设 $f_{i,j}$ 表示考虑到第 $i$ 行，该行的分界线在第 $j$ 列处时的最小值，不妨认为初始所有点都在右下，那么左上的所有 $1$ 贡献 $-1$，所有 $0$ 贡献 $1$，如此可以做到 $O(n^2)$ DP。
由于整个矩阵中的值都是递减的，所以不同值的分界线一定是从左上到右下的若干条折线。考虑用一个整体二分来求出所有折线，取 $mid$ 后把目前剩余的所有限制分成最终值大于 $mid$ 和不大于 $mid$ 两部分，那么可以认为左上所有大于 $mid$ 的限制贡献 $-1$，所有不大于 $mid$ 的限制贡献 $1$，这样 DP 只需要还原一下方案，就可以把所有限制分成两半，递归下去整体二分即可，时间复杂度 $O(n^2 \log n)$。
注意到 DP 的操作为后缀加和对后缀取 min，因此维护 DP 值的差分数组，一个 $1$ 的贡献会直接加到差分数组里，一个 $-1$ 的贡献可以消去其前面或相同位置上的一个 $1$。用 set 维护所有 $1$ 的位置，过程中记录一下 $-1$ 所消去的 $1$ 的位置。由于需要方案，需要倒着还原 DP 数组，这里记录目前分界点 $p$，若出现 $-1$ 没有用过从而留在了 DP 数组中，或是消去了 $p$ 及其前面的一个 $1$，那么将 $p$ 后移至该 $-1$ 的位置一定不劣，于是我们做到了 $O(n\log n)$ DP。总时间复杂度为 $O(n\log^2n)$。
原题
QOJ8522。
2.25T1 翻转
题意
定义长为 $n$ 的排列 $p$ 权值为：依次处理 $i\in[1,n]$，找到 $p_x=i$，然后翻转 $[x,n]$，权值为 $n$ 次翻转的区间长度之和。多次询问给出 $n$，要求构造权值尽可能小的 $p$。评分标准为设 $P$ 为给出排列的权值，$q=n\log_2 n+\lfloor \frac n{12}\rfloor +5$，若 $P>2Q$ 则不得分，否则每个点的分值 $W=20$，得分为 $W\min(1,1-\log_2(\frac PQ))$，四舍五入取整。$T\le 10,n\le 10^5$。
题解
首先注意到把 $1$ 放到结尾一定不劣，但是没什么用。再注意到长为 $n$ 的排列可以从 $mid$ 处分为两部分，后半部分直接递归下去构造 $\lfloor\frac n2\rfloor$ 的答案，再将下一个数放到序列开头，从而在下一次操作中把前半部分翻转到后半部分。注意到这个数翻到了最后，也即 $1$ 应该在的位置，所以直接递归构造 $\lceil \frac n2\rceil$ 的答案并翻转一下即可。
求权值可以直接暴力求，也可以递推全部预处理出来。这样构造的排列权值 $P$ 最多会比 $Q$ 大大约 $400$，然而四舍五入后可以得到满分。时间复杂度 $O(n\log n)$。
2.25T2 编号
题意
定义长为 $n$ 的排列 $p$ 权值为：将其分成极长值域上连续段，权值为这些段的最大长度。求 $n!$ 种排列的权值之和，对给定的模数取模。$n\le 3000$。
题解
若把值域分成 $i$ 段，那么这 $i$ 段之间的排列方式需要满足第 $j$ 段不在第 $(j-1)$ 段后面相邻。可以设 $g_{i,j}$ 表示放了前 $i$ 段，且 $(i-1)$ 个相邻对中有 $j$ 个不合法的方案数，那么合法排列方式数即为 $g_{i,0}$，$O(n^2)$ 即可 DP 预处理求出。
那么还需要求把值域分成 $i$ 段，且最长段长度为 $j$ 的方案数。直接容斥 + 隔板法，钦定 $k$ 段长度至少为 $j$，剩余长度再组合数分。同时由于已经钦定过的可以为空，而没钦定过的不能为空，可以先给钦定过的减少 $1$，转化为全部不能为空的情况。因此该方案数为 $\sum_{k=1}^{\min(i,\lfloor\frac nj\rfloor)} (-1)^{k+1}\times {i\choose k} \times {n-(j-1)k-1\choose i-1}$。再乘上 $g_{i,0}$ 累加给答案即可。时间复杂度为 $O(n^2\ln n)$，来自枚举 $k$ 的调和级数。
鲁ICP备2025150228号