做题记录

$\color{navy}\texttt{P13275 [NOI2025] 集合}$

思考：

随便容斥，交换求和后有 $4^n$ 做法，需要求逆元有 $0$，记录一下 $cnt$ 判断即可（$cnt_x+cnt_y=2cnt_{x|y}$），如果没有 $0$ 可以 FWT $2^n n$

sol：

注意到 $cnt$ 在超集上具有单调性，将式子改为 $cnt_x=cnt_y=cnt_{x|y}$，仅在 $cnt$ 相同时转移 FWT 即可

$\color{purple}\texttt{P3598 Koishi Loves Number Theory}$

sol：

$\text{lcm(f(a), f(b))}$ 形式复杂，$\text{gcd(f(a), f(b))}$ 形式简单，使用 min-max 即可

upd：ARC202(Div. 1) 的 C 题考了这玩意，我在考前一天做了这道题（

$\color{purple}\texttt{P10440 [JOISC 2024] 环岛旅行}$

思考：

求出到 $1$ 距离的排序，从后往前，每条边至多问两遍，查询 $3n$ 次

sol：

从前往后即可查询 $2n$ 次，不知道为啥没想到

$\color{purple}\texttt{CF1889D Game of Stacks}$

思考：

扫了眼题解，看到了忽略环，遂会了。

对于 $i\to s_i\text{.back}$ 形成的基环树，把环上的每个点的栈 $\text{pop}$ 后对结果没有影响。如上操作完最后的图是若干内向树，$i$ 的祖先是 $ans_i$。考虑进行原题中 $\text{get(i)}$ 操作，除了没有影响的弹掉了若干个环，还破坏了 $i\to ans_i$ 链的栈，对链上每个点记录下他的答案（以后进入直接使用 $ans$ 不再递归）即可。换言之，每次 $\text{pop}$ 要么弹掉了环没有影响，要么把最终的树边做了“路径压缩”。

$\color{navy}\texttt{P3571 [POI 2014] SUP-Supercomputer}$

思考：

每个点的最优解从儿子的最优解合并而来这种想法看上去很唐，只能从上往下处理。

先猜贪心，能选的中优先选到叶子距离最长的，不会证明找不到反例。然后猜答案是层数 $\le i$ 的用了 $i$ 次，剩下的每次 $k$ 个都能卡满，对所有 $i$ 求最大值，感觉很对，写了个暴力得了 TLE 91pts，太震撼了，随便写个李超树就过了。

sol：

自己想了一下证明。

对于 $xk+sum_{x+1}$ 的每个前缀最大值，都可以从上一个每次操作满 $k$ 转移来（最后一次除外），可以证明能用层数次操作消完。后面的能每次用满 $k$ 次操作也是同理证明。

$\color{purple}\texttt{CF1361C Johnny and Megan’s Necklace}$

思考：

欧拉回路板子。

$\color{purple}\texttt{ABC277Ex Constrained Sums}$

思考：

两数求和先想了切糕，发现好像流不了，不幸得知正解是 2-SAT 于是开始猜每个点只有两个有意义取值之类的幽默玩意。

sol：

记录 $nm$ 个 $[a_i\le j]$ bool，本质状态设计还是切糕，2-SAT。

$\color{navy}\texttt{CF1458D Flip and Reverse}$

思考：

转成 $1,-1$ 求前缀和，丢到二维平面上去，不会了。

sol：

把二维平面 $(i,sum_i)$ 的 $i$ 去掉，变成 $p\to p-1\text{ or }p+1$，操作即为翻转一个环。任意一条欧拉路径都可以和原序列转换。证明：如果在 $p$，第一次不同，如原图往上最优解往下，$p$ 往上往下走均可以走回到 $p$，可以通过翻转使得原图和最优解的这一步相同，然后向钱看，归纳证明。

$\color{purple}\texttt{P3175 [HAOI2015] 按位或}$

思考：

min-max 板子。

$\color{purple}\texttt{CF932E Team Work}$

思考：

$i^k$ 转组合，做完了。

$\color{navy}\texttt{AGC055F Creative Splitting}$

思考：

考虑判定。把每个数变成一个 $\ge$ 自己的。从前往后扫，要求任何时刻 $cnt_i\ge cnt_{i+1}$。无论从前往后还是从后往前都无法唯一确定当前决策。考虑类似反悔贪心，后面可以修改前面的决策，即为把一个数继续变大，但是还有问题。比如说 $cnt=[5,3,3,0]$，来了一个 $3$，此时出现了不合法，但是无法确定应该变成 $[5,3,3,1]$ 还是 $[4,4,4,0]$，这两种方案不能互相转化，也无法偏序。真能判定吗？做法应该是找到了一个 Hall 定理一样深刻的判定，或者不用判定也能计数？

真唐，从后往前就是对的，$[1,2,3],[1]$ 就是严格优于 $[1,2],[1,2]$ 的，手玩玩错了/ll

sol：

判定：从后往前贪心，维护 $n$ 个数，初始为 $k$，每次来一个数 $i$ 把 $\ge i$ 的最小的 $-1$。正确性证明：归纳，假设需要插入 $i$ 个数这是对的，插入 $i+1$ 个数的最优策略就是这个，显然 $i,j+1$ 比 $i+1,j$ 在这个策略下更有用（$i<j$）。

这个楼梯状物不好维护，把他放倒（转置），现在变成，有 $k$ 个数初始为 $n$，并记录初始 $id$，来了 $nk$ 个数（有一个限制了值），来了 $i$ 就把 $\text{pair}(val, id)$ 第 $i$ 大的 $val-1$，注意到每个 $\text{pair}$ 每次恰有一种被选中的方案，于是除了限定的 $pos$ 次其他次就相当于随便找一个数 $-1$，只用在乎 $pos$ 次时的楼梯形状。

假设即将进行 $pos$ 次操作时，$val$ 从大到小为 $a_1,\cdots,a_k$，贡献为（$b_{pos}=v$）：

$$k!\times\frac{(pos-1)!}{\prod (a_i-[i=v])!}\times\frac{(nk-pos)!}{\prod (n-a_i)!\times \color{blue}\prod_i(\sum_j [a_j=i])!}$$

最后那个是因为 $a_j$ 相同的内部顺序没有影响，$k!$ 是映射到初始的 $id$，看了 sol 自己想的时候没想到要乘这两个，感觉是这个原因。

$\color{purple}\texttt{P3511 [POI 2010] MOS-Bridges}$

思考：

二分一下，变成了有向边和无向边（只能走一次）判定欧拉回路，想直接 dfs 的时候构造+判定，但是做不了。

sol：

一定连通，考虑每个点入度等于出度，每条边选择给 $u/v$ 的 $f+1$，要求 $f_u=\frac{deg_u}{2}$，网络流即可。

$\color{navy}\texttt{P13272 [NOI2025] 序列变换}$

这一世，我重生了，后面忘了。

思考：

听到别人讨论，应该考虑判定 $A$ 是否可以变成 $D$，考虑是否变成 $S(D)$ 是愚蠢的，因为第二问就根本做不了，但是我场上想这玩意很久。每个改变的值旁边至少有一个 $0$，考虑改变的连续段，本质上一定是 $10002$ 这种东西。（引理：把一串数全变成 $0$ 本质上是从左往右顺序消，考虑最边上的显然。）

考虑第一个操作产生的 $0$，最终一定是从这个 $0$ 往左，右按顺序一串操作过去。证明：如果产生了两个 $0$ 夹着一些非 $0$，把非 $0$ 变成 $0$ 一定是一串操作过去，可以先操作好，这样也符合顺序。考虑 $xabcdey$，$\triangle x=-a+b-c,\triangle y=-e+d$，注意还会有一些大小关系限制使得它能一路操作过去，不是所有的这种类型都符合。在上面柿子中，对于 $c$，它能操作到的点事一个区间，但是对于 $x$ 没有这种形式的限制。现在就有了一个判定：找到变化完形如 $a000b00c0000d$ 这种形态的东西，利用奇偶位和算出来每个数被左/右分别减了多少，对于 $a000b$，随便在中间找一个符合 $a$ 的值的位置往左操作（如果有多个符合中间变成一堆 $0$ 没啥影响），看他能不能操作到 $b$。这判定能tm记数吗。 首先变成找最左边的符合 $a$ 的，这样双射，且 $ab$ 基本独立，但是每个数被左边减的值和被右边减的值很重要，减完必须 $>0$，这样至少是三次方的了。

sol：

以上分析正确。注意到，答案形式 $[00a00][0b00][c00]$ 本质上是一个区间聚集到了一个点上，而可以作为最终结果的点的集合具有良好性质（$i\bmod 2=k,i\in [l,r]$），预处理即可省去枚举中间点。利用上文所说找第一个右端点的性质，可以做到计数双射。

关于双射，我的想法貌似和题解不太一样（还没写不知道正确性）。对于 $[000a000]$，要求 $a$ 的左右均不能从端点产生一个 $0$，比如说 $[1,1,2,10,1]$ 应该分割为 $[1,1][2,10,1]$。全为 $0$ 的段也不应该能被分割。从左往右扫，能分割就分割，看上去很双射啊。

upd：是对的。

$\color{navy}\texttt{ABC274Ex XOR Sum of Arrays}$

思考：

设计一个可异或的哈希判断数组是否全为 $0$。我想的是 $\oplus_{i,j}(f_{i,j}\cdot a_i\cdot2^j)$，其中 $f_{i,j}=\text{rand}(0/1)$，复杂度 $\text{O}(n\sqrt{m\log v})$，不知道能不能过。

sol：

类似的把一位映射到一坨，采用的是把数视为 $01$ 向量，用异或矩阵乘法，即为 $h_i=(h_{i-1}\times I)\oplus val_i$，复杂度 $\text{O}(n\log n\log V+m\log n)$，其中 $n=5\times10^5,m=5\times10^4$，为开数据范围的人点赞。正确性不会证，看上去就很对。

$\color{navy}\texttt{UOJ 840 龙门考古}$

思考：

选出来的 $0,1$ 子序列一定是单增的。判定。先考虑从前往后看每一个 $S$ 中元素能否填更小的，做不了。猜了一个贪心找字典序最小的策略：考虑 $01$ 序列带来的大小关系限制形成的树，小到大枚举值，填入没有入度的编号最小的。最小证明：$\forall c,\sum [a_i\ge c]\cdot 2^{n-i}$ 均取到最小值，说人话就是按大小关系赋 $01$ 序列是最小的（好新奇的字典序最小证明）。合法证明：$S_1$ 序列也是字典序最小，比 $S_1$ 小的关系用树保证了，由于字典序最小，不可能出现 $S_1$ 过大的情况（即 $a(S1)\cdots b(1), a>b$ 的情况）。

sol：

官解给了一个很幽默的判定，不过做法基本不基于判定。找一些合法的必要条件，考虑调整。对于一个 $S_1$ 点 $i$，假设后面的下一个 $1$（无论是否在 $S$ 中） 在 $j$，$[1,j)$ 中除了 $a_i$ 最大值为 $v$。若 $a_k\le v$，交换 $i,k$ 是非法的。若 $v<a_k<a_i$，此时 $k>j$ ，交换 $i,k$ 合法且使字典序更小，所以如果 $i$ 被选中，$a_k\in(v,a_i)$ （称之为判定区间，这些区间两两不交）的 $k$ 会被强制无法选中。官解声称如果满足这个就是充要的。考虑用我的判定来归纳证明：当前最小值 $\min$ 只能填入第一个 $S_0$ 或者第一个 $S_1$（不一定填得了，如果可行一定在 $0$ 前面），可能产生非法的方案只有 $01$ 都能填（称两位置为 $p0,p1$）但 $a$ 序列的方案填在了 $0$，此时有 $a_{p0}<a_{p1}$，为了不与上文“强制无法选中”矛盾，可得 $a_{p0}<v$，此时 $v<\min$，$p1$ 一定有没有删除的入度，矛盾！考虑记数，选出 $0$ 的上升子序列 $S_0$，如果一个判定区间与 $S_0$ 无交，这个 $1$ 点可选可不选，贡献 $\times 2$，随便 $dp$ 即可。

$\color{navy}\texttt{AGC038E Gachapon}$

思考：

min-max。把 $A_i$ 变概率，达到指出现 $A_i$ 次。

$$ans=\sum_{S,S\not= \varnothing} \frac{E(S第一次达到)}{\sum_{i\in S} A_i}\cdot (-1)^{|S|+1}=\sum_{S,S\not= \varnothing} \frac{\sum_{i=0}^\infin P(S第i步没达到)}{\sum_{i\in S} A_i}\cdot (-1)^{|S|+1}$$

这不就做完了？$dp_{i,j}$ 代表已选的 $S$ 中元素 $A$（不除 $S$）和为 $i$，操作了 $j$ 步。如果选：

$$dp_{i+A,j+k}\leftarrow -dp_{i,j}\cdot\frac{1}{k!}\cdot {\color{red}A}^k\ (0\le k<B)$$

写挂了看了 sol，发现这里的 $A$ 其实应该是 $\frac{A_i}{\sum_{j\in S}A_j}$，无语了

$\color{navy}\texttt{AGC066E Sliding Puzzle On Tree}$

思考：

如果不考虑标号，任意两种方案都可以互相转换，懒得证。考虑所有石头最终在节点 $1\sim k$（或者任意指定的 $k$ 个点），答案就是这样的方案数 $\times C_n^k$，易证。猜想本质上就是可以交换若干点对（即所有的序列可以用 $\text{swap}$ 互相转化，并且 $\text{swap}$ 过程中每个序列都合法），这样就可以维护连通快。考虑把任意一个方案映射成一个序列，这样我们就可以考虑这个序列第一次发生变化的时候。证明：令 $k$ 个点的选法为每次找一个叶子并删除（使得其父亲可以成为叶子），按顺序设为 $a_1,\cdots a_k$。对于 $a_i$（此时他的子树内都填上了石头），寻找一个到它的路径上没有障碍的点挪过来，显然一定可以完成。考虑什么时候这个策略无法得到最初序列，只能为 $a_i$ 在尝试找 $b$ 的时候被上一步移动的 $c$ 堵住，让 $a_i$ 匹配 $c$，其他不变，原本匹配 $c$ 的匹配 $b$，显然可行。证毕。冲击 $\text{poly}(n)$！考虑 $a,b$ 是否连边，即是否能操作使得有一个无石头的点，连接了 $a,b$ 和一个无石头的点。如果 $a,b$ 路径间有一点 $c$，若 $(a,b)$ 有边，$(a,c)(b,c)$ 必然也有边（感觉很对懒得证），没有必要考虑 $a,b$，$a,b$ 要么直接连边，要么父节点均没有石头。

sol：

还没看懂。

$\color{purple}\texttt{ARC201D Match, Mod, Minimize}$

思考：

二分，匹配，Hall，线段树，$2\log$。

sol：

可能是由于注意到上文的匹配区间是环上的 $M-a_i$ 开始的等长区间，令 $a_i\leftarrow -a_i\pmod m$，$ans=\max(b_i+c_iM-a_i)$，当 $c_i$ 确定，将 $b_i+c_iM$ 排序即可计算得到答案，显然 $b_1,b_2+M$ 不如 $b_2,b_1+M(b_1<b_2)$，所以一定选取一个前缀 $+M$，二分前缀长度即可。

$\color{navy}\texttt{P4707 重返现世}$

思考：

来学 min-max，会了 $\text{kthmax}$ 自己推一下试试。如果认为是 $k$ 大，钦定的集合大小 $\ge k$，这样可以利用 $n-k$ 的限制，不过需要求 $\max$ 比较烦，如果改成求 $\min$ 又没有集合大小的限制了。这个组合数是不是可以转组合啊，那岂不是做完了。

$$ans=\sum_{S}\frac{m}{\sum p}\cdot C_{|s|-1}^{n-k}\cdot(-1)^{|S|+n+k+1}$$

有个难绷的地方，这个题数据 $n$ 都是偶数，所以有一个做法通过了但是样例输出相反数。

$\color{purple}\texttt{YDRG011F. 抽卡}$

思考：

首先 $k$ 次幂转组合，考虑选 $k$ 次（好像是斯特林数的恒等式）。$f_x$ 为 $1\sim x$ 都只抽了一次卡：

$$ans=\sum f_i\cdot A_n^i\cdot {k\brace i}$$

对于固定的 $x$ 求 $f_x$：设 $dp_{i,j}$ 为还剩 $i$ 个 $1\sim x$，$j$ 个剩下。

$dp_{i-1,j}\leftarrow dp_{i,j}\cdot \frac{i}{x+j},\ dp_{i,j-1}\leftarrow dp_{i,j}\cdot \frac{j}{x+j}$

复杂度为 $nm^2$。分子可以去掉，现在变成了 $(k,n)$ 走到 $(k-x,x)$，求 $y$ 坐标的倒数的乘积。这就可以复用信息了。$\text{O}(nm)$。

$\color{purple}\texttt{P6620 [省选联考2020] 组合数问题}$

思考：

$$\sum k^ax^kC_n^k$$

$$=\sum_k \sum_i A_k^i{a \brace i} x^k C_n^k$$

$$=\sum_k \sum_i A_n^i {a \brace i} x^k C_{n-i}^{k-i}$$

$$=\sum_i A_n^i {a \brace i} x^i(x+1)^{n-i}$$

$\color{navy}\texttt{P11834 [省选联考 2025] 岁月}$

思考：

权值相同本质上是边权的出现次数相同。考虑 Krustal 加入边权 $\le i$ 产生的连通快集合。令集合 $S$ 中可以通过有向边走到所有点的集合为 $t(S)$。假设加入边权为 $a$ 的边后，把集合 $S_{2,3,4}$ 合并为集合 $S_5$。假设图的磨损已经确定，将无向边拆成两条有向边，称 $u\to v$ 是合法的边当且仅当 $v\in S_{2/3/4}$。若 $t(S_2)\cap t(S_5)\not= \varnothing$，$t(S_2)\subset t(S_5)$，这个的充要条件是将连通快看成点后，$S_2$ 通过合法的边可达 $S_{3,4}$。对于每一种状态，找出合法边，求出缩点后的 $\text{scc}$ 外向树的根 $\text{scc}$ 组成集合概率分布即可转移。假设合并了 $a$ 个集合，这 $a$ 个集合的 $t(S)$ 至多有 $2^{n-a}$ 种，每种做主旋律是 $3^n$，可以分析得总复杂度为 $3^n$，代码不想写。

$\color{purple}\texttt{CF1976F Remove Bridges}$

思考：

原树中不是桥的充要条件是在某条加边 $u_i,v_i$ 的路径上，证明显然。猜想：由第 $i-1$ 步的最优解可以得到第 $i$ 步的最优解。错的。$1\to 2\to 3,4$，然后 $3$ 下面挂一条 $100$ 长的链，$4$ 下面挂三条 $95$ 长的链。第一步的最优解是走 $3$ 方向，但两步最优解可以把 $4$ 的两条链和 $3$ 全消掉。咋感觉答案就是选至多 $2k$ 个叶子（必须有 $1$），然后求类似虚树大小（原图中连接任意两选中点的边）。证明：首先可以用 $k$ 条边得到这个虚树，并且每条非桥的边祖先都非桥（题目应该是加完 $k$ 条符合就行，不过每加一条都符合条件也能做到）。可以树上 $dp$：$dp’{u,i+j}\leftarrow dp+dp_{v,j}+[j>0]$。这是不是有凸性，那不是闵和做完了。听说题解不用凸包，发现这个过程好像在不停地揪一条最长链，利用删边总和一定，可以线段树维护，$\text O(n\log n)$。题解貌似可以长剖线性，但我不会长剖/cf。

$\color{purple}\texttt{CF1967E1 Again Counting Arrays}$

思考：

一个序列不合法必须有一个位置 $b=0$ 且下一个禁止放 $1$。感觉只要不与 $a$ 矛盾，$b$ 就应该尽量选大的。考虑归纳证明，对于所有奇偶性对的点，大的不比小的劣。归纳即可。现在问题转化为在 $(0,b_0)$ 开始走，往右上一步系数 $\times (m-1)$，往右下不变。如果 $y$ 坐标达到了 $m$ 立即失败，达到了 $-1$ 立即成功（不合法）。枚举第一次达到 $-1$ 前的 $(a,0)$，然后变成了 $y=-1,m$ 都不能碰，反射容斥即可。复杂度 $\min(nm,\frac{n^2}{m})=n\sqrt{n}$。

$\color{purple}\texttt{CF2002F2 Court Blue}$

思考：

从原点走到目标点，且不得经过 $x,y$ 不互质的点。打表，发现 $y=x$ 将平面隔离开，并且利用质数可以达到一个及其接近最优解的答案。假设 $m{\color{red}<}n$，观察表发现，令 $t$ 为 $\le n$ 的最后一个质数，一定可以走到 $(t,m)$， $(n,p)\ (\forall i\in [t,n],\gcd(p,i)=1)$，显然，答案只能在 $[t,n]\times [p,m]$ 的这个矩形中，并且这个矩形的两条边长大约均为 $\text{O}(\log n)$ 的（$p-m$ 可以证明至多是 $\omega(n)\log^2 n$ 的，但是显然取不到，并且 $(n,m)$ 不同大概也暗示了这个做法）。最终复杂度是 $\log^3\sim \log^4$ 的。你别说，写完跑的真很慢。

CF 啥时候题质量这么高了？

$\color{purple}\texttt{CF2068E Porto Vs. Benfica}$

思考：

看题目名进来的。

为啥感觉开始一定要沿着最短路走（错的）。有点 $\min_{path}(\max_{edge})$ 的感觉，是不是可以二分一下？显然警察如果决定封堵，一定是堵球迷现在位置 $u$ 到 $n$ 的最短路，然后球迷走剩下图中最短路（设为 $t_u$，虽然我还没想怎么求）。若 $dis_{1,u}+t_u\le mid$，那么 $u$ 不可堵，否则 $u$ 可堵，球迷走到这里就失败了。感觉如果 $1,n$ 通过不可堵的点连通了，那么可以找到从 $1\to n$ 的不可堵路径，其中每条边走完后到 $1$ 的距离都会 $+1$，球迷就赢了。好像也不对，可以走 bfs 树的反向边。有一个复杂度大的做法，每次把不可堵的点删掉，$t_u$ 不变，重新求 $dis_{1,u}$。这个轮数看上去很少啊，总不能把这个卡到 $\text O(n)$ 轮吧。

题解：

先不管 $t_u$ 怎么求。设 $f_u$ 为球迷在 $u$，警察还没封堵，答案为多少。有 $f_u=\max{t_u,1+\min_{(u,v)\in E} f_v} (u\not= n)$，正确性显然。知道 $t$ 之后用堆即可。考虑求 $t_u$，显然一定删除 $u$ 到 $n$ 的最短路第一条边，把到 $n$ 最短路树建立出来。

$$t_u=\min_{(x,y)\in E,x\in \text{subtree(u)},y\notin \text{subtree}(u),y\not= fa_u}(dis_x+dis_y-dis_i+1)$$

求 dfn 线段树合并即可，洛谷疑似有更简单的做法，但是我没看懂，并且好久没写 ds 了。