当前位置：首页 > news >正文

202507做题记录

news 2025/10/19 10:20:43

加粗斜体表示思考时被卡了的部分。

2025 省队集训

省集 0701 A tree

首先对每个点执行 \(f(i,1)\)，这样我们发现，除了根和叶子，每个点恰好被计算三次。根被算两次，叶子只有一次。

然后只要找到根，就可以比较简单的单独计算叶子，同时也可以简单得到根的值。

我们考虑，根就距离最远点的距离是最近的，\(=h-1\)，但是因为我们要得到根的值，所以同时需要得到根的两个儿子是谁，所以我们先查询 \(f(i,h+1)=0\) 的，一共三个点，然后在这三个点里查询 \(f(i,h)=0\) 就是根。

然后叶子的值不用单独算，我们注意到根的儿子的 \(f(i,h)\) 之和恰好包含了对侧子树的所有叶子，拼起来就是整个树的叶子。

然后求根的值，先查询 \(f(rt,2)\)，然后求出和两个儿子 \(f(i,1)\) 的和的差值就行了。

精细实现一下，做到 \(2n+3\) 次，每个点询问不超过 \(4\) 次。

省集 0701 B loong

考虑钦定 \(j,b_j=\min b_i\)，然后我们发现，要求就是，\(\forall i\in S\setminus j，a_i<b_j\land b_i>a_j\land b_i>b_j\)，然后分类讨论：

对于 \(a_j<b_j\)，我们发现就是对 \((b_j,b_j)\) 左上角的矩形数点，这是简单的。
对于 \(a_j>b_j\)，我们发现是对 \((b_j,a_j)\) 左上角数点，比较困难。

注意到最多选择一个 \(a>b\) 的点，所以答案一定只比情况 \(1\) 最多多 \(1\)。

所以变成判定是否会多 \(1\)。

我们维护互相不偏序的 \(a>b\) 的 \((a,b)\)，然后维护这些合不合法，注意到合法的条件：

\((b,b)\) 左上角的矩形数点答案是情况 \(1\) 的最大值。
\((b,b)\) 左上角的矩形中，没有任何点 \((a',b')\) 的 \(a'>a\)。

注意到，加入一个 \(a<b\) 的 \((a,b)\)，会对条件 \(1,2\) 进行区间修改，同时两个相邻区间信息可以合并，所以可以上线段树。

这样我们把他放到线段树上维护，复杂度 \(O(n\log n)\)。

省集 0701 C lush

先考虑暴力，有一个树上背包，大概长成 \(f(i)g(j)\to h(i+j-k),k\in[0,\min(i,j)]\)。

然后肯定是大胆猜测有凸性，这是对的。

考虑按照斜率正负分成左右两侧，设 \(f,g\) 的分界线是 \(n,m\)。

然后考虑对于右侧斜率为正的，就是闵可夫斯基和，直接合并。同时 \(k=0\)。我们就得到了 \(h(i\geq n+m)\)。

对于斜率为负的，\(k=\min(i,j)\)。这里可以得到 \(h(i\leq |n-m|)\)。

先看一下什么时候会取到 \(k\in(0,\min(i,j))\)，就是斜率为负到斜率为正的中间那一段。也就是 \(h(i\in (|n-m|,n+m))\)。

显然比较困难的就只是 \(h(i\leq |n-m|)\) 这段。

先考虑 \(h(0)\)，找到 \(fp=gp=p\)，使得 \(h(0)=f(fp)+g(gp)\)。

然后考虑 \(h(1)\)，肯定是从 \(h(0)\) 的基础上调整而来的，所以考虑只需要移动 \(fp\) 还是 \(gp\)。

假设 \(fp\) 位于斜率负区间，\(gp\) 位于斜率正区间，那么一定是右移 \(fp\) 或左移 \(gp\)。

考虑哪种移动优秀就用哪种移动。这个的意义其实就是把某段斜率翻转取负，然后归并。

复杂度就是 dsu on tree 的 \(O(n\log^2 n)\)。

省集 0702 A trans

首先无解的充要条件就是存在 \(i\) 使得 \(\sum_{j\leq i}a_j>0\)。

考虑令 \(b_i=a_i+a_{i+1}+a_{i+2}\)，然后我们发现，一次操作只会改变 \(O(1)\) 个 \(b\)。具体的：

\(b_{l-2}+1,b_r-1\)，操作形如 \(1,-1,0,\cdots,1,-1\)，所以 \(l+1\equiv r\pmod 3\)
\(b_{l-2}+1,b_{r-1}+1,b_r+1\)，操作形如 \(1,-1,0,\cdots,1\)，所以 \(l\equiv r\pmod 3\)。同时，被加 \(1\) 的 \(b\) 的位置 \(\bmod 3\) 不同。

因为操作 II 一定会让 \(a\) 的和增加 \(1\)，所以操作 II 的次数一定为 \(-\sum a\)。

然后我们注意到比较特殊的就是这个 \(b_r-1\)，所以考虑倒着做：

如果当前 \(b_i>0\)，那么一定是操作 I，所以一定需要一个 \(l<r\) 使得 \(l+1\equiv r\pmod 3\)，然后 \(b_l+1\)，先记着。
如果 \(b_i<0\)，需要讨论一下。
- 如果 \(b_{i-1}<0\) 同时还可以进行操作 II，那么优先操作 II，记录需要一个 \(l\equiv i+1\pmod 3\)，让 \(b_l+1\)。
- 如果上面一步后，\(b_i<0\)，那么消耗之前记着的 \(l\) 的个数。
- 如果消耗完了，那么只能使用操作 II（此时会让 \(b_{i-1}\) 变为正值）。

因为一定有解，同时这个做法是最优秀的，所以不会出现操作 II 过量的情况。

省集 0702 B toxic

考虑如果已知一种细菌是有毒的（记为 \(T\)），那么如何一次尽可能多的确定细菌是否有毒。

首先可以想到的是，使用形如 \(Ta_1Ta_2a_2a_2T\cdots T((2k-1)\times a_k)T\)，这样我们通过每轮操作删除细菌的奇偶性可以判断细菌的毒性，\(k\) 可以做到 \(31\)。

然后考虑我们只用到奇偶性，比较不牛，考虑一种比较劣的做法是，\(Ta_1Ta_2a_2T\cdots T(2^{k-1}\times a_k)T\)，这样只要看最后剩下多少就可以知道毒性。

这个做法的优点是，不需要看中间过程，所以考虑合并这两种做法：

令 \(f(k,c,i)\) 表示 \(2^k\times (T(2c\times a_i))\)，我们注意到，这一串会影响第 \(c-1,c,c+1\) 轮剩下细菌个数的二阶差分，然后把 \(k>0\) 的 \(f(k,c,i)\) 的代价和前面 \(Ta_1Ta_2a_2a_2T\cdots T((2w-1)\times a_w)T\) 的代价，贪心决策选择哪一些 \(f\)，以及 \(w\) 选择多少。

然后你发现只这样做，只能做到 \(49\) 个一组，然后注意到，我们可以在两侧塞上 \(k_1\times a_i,k_2\times a_j\)，此时一轮最多分别删除 \(a_i,a_j\) 一个细菌。如果 \(k_1,k_2\) 比 \(\max(w/2,c)\) 大，那么一定是删的最久的，可以单独计算得出 \(a_i,a_j\) 是否有毒。然后选择前 \(48\) 优秀的方案，然后两侧拼上这玩意，刚好可以塞进 \(1000\)。

然后需要在 \(1\) 次操作里找到有毒细菌。首先可以查询 \(1,2,\cdots,499,500\times 500\)。然后根据这次操作一共持续几轮，只要不是全 R 或全 T，那么一定可以找到一个 T。

如果左侧是全 R 或者全 T，那么在右侧再进行一次操作得到 T，然后通过这个 T 判断左侧是 R 是 T。因为可能刚好左侧全 R，右侧全 T，这样你查不出来，所以可以打乱询问的点，这样只有指数倒数级别的概率会出现这种问题。

然后如果第一次找到 T，就满足要求，如果第二次才找到 T，注意到我们已经确定左侧的所有细菌的类型，所以我们只要找剩下 499 个细菌的类型，显然只需要 \(10+3=13\) 次。

所以最差情况下 \(21\) 次。

省集 0702 C second

拆贡献，二维数点题。

省集 0703 A sand

稍微推一推就行了，注意计算某一些值的时候，可以从组合意义的角度考虑，复杂度可能会好很多。

省集 0703 B tree

厉害题，赛时只会剥一层叶子。

先看 sub1。

考虑一层一层剥叶子，首先第一层是简单的，只要询问全集扣掉 \(i\)，看答案是否为 \(n-1\) 即可。

然后已知当前叶子，当前待剥的点，需要找到新的可以剥的点。

考虑一个点可以剥当且仅当其两个儿子全部剥出，所以我们记录当前叶子的父亲，然后看哪些点 \(u\) 出现两次（\(u\) 的两个儿子全部出现），那么把 \(u\) 加入叶子集合，把 \(u\) 的儿子扔出集合。

这样通过不断操作，最后一定可以确定所有父亲。

考虑如何确定一个点 \(i\) 的父亲。

设当前叶子集合 \(leaf\)，待剥去集合 \(u\)，那么有性质：\(leaf\) 的虚树 \(t(leaf)=(V,E)\) 满足 \(V=leaf+u\)。

并且 \(V(leaf\setminus i)=leaf\setminus i+u\setminus fa_i\)。

所以我们判定 \(fa_i\in S\)，只要判定 \(V(leaf\setminus i+S)=|leaf|-1+|u|\)。

这样我们通过二分，可以在 \(O(n\log n)\) 次查询中得到答案。

然后是 sub2，我们注意到，一棵树无解当且仅当存在一对父子 \(u,v\) 都最多只有一个儿子。

所以解决 sub2 的思路就是，找到由所有 0,2 个儿子的点组成的虚树，然后树边上最多有一个只有一个儿子的点。

我们先通过 sub1 一开始的查询，可以查询出一个点有两个儿子还是其他情况。

然后把其他情况记为 \(S\)，然后考虑求出叶子，通过查询 \(S\setminus i\) 可以确定 \(i\) 是否是 叶子并且父亲有两个儿子。

如果是叶子并且父亲只有一个儿子一定无解。所以我们不管他。

然后通过 sub1 的方法我们得到了由所有 0,2 个儿子的点组成的虚树，然后接下来定位有恰好 1 个儿子的点在那条边上。

考虑在树上二分可以用重剖，我们从根节点开始。设当前判定到以 \(x\) 为根的重链。

先用一次操作判定是否在 \(x\) 重链上，如果在重链上直接二分。

如果不在重链上，需要带一个轻儿子重量的权值进行二分才能保证复杂度为 \(O(n\log n)\)。

省集 0703 C future

暴力平衡树维护。需要注意的是：

\(\sum_{i=0}^k ix^i=(k+1)\sum_{i=0}^kx^i-\sum_{i=0}^{k-1}\sum_{j=0}^ix^j\)。然后内层求和可以用等比数列求和转化，然后发现转化完之后又是一个等比数列求和，然后做完了。

平衡树节点的 split：

如果一个节点维护的是一个区间（不是指子树区间），在 split 的时候可能需要分裂该节点。

使用 fhq 时需要特别注意分裂方法，需要把分裂出来的新节点进行一次 merge，因为新节点的优先级不可以是原节点的优先级，同时新随机的优先级不一定满足堆的性质。

或者直接使用无优先级随机合并的 fhq。

省集 0705 A plan

先把 \(a,b\) 升序排序。

首先如果已知谁赢谁输，那么显然让赢的按顺序对战前面弱的怪物，输的按顺序对战后面强的怪物。

考虑朴素 dp，枚举有 \(k\) 人会赢，设 \(f_k(i,j)\) 表示 dp 到 \(i\)，选择了 \(j\leq k\) 个赢的人的方案数。

注意到这个 dp 的转移是和 \(k\) 有关系的，因为要判断第 \(i\) 个输掉的人是否会比 \(b_{k+i}\) 小。

这样做是 \(O(n^3)\) 并且不好优化。

考虑已经枚举了 \(k\)，对于 \(a_i<b_k\)，显然只要他选择输，一定会输，但是选择赢不一定会赢。

同理，对于 \(a_i>b_k\)，只要选择赢，一定会赢，否则不一定输。

所以我们只关心 \(a_i<a_k\) 有几个会赢，此时的 dp 我们并不关心钦定输的人，因为最后计数的时候，钦定输的人一定输。

同理，我们只关心 \(a_i>b_k\) 有几个会输。

所以在 dp 的时候我们不需要枚举 \(k\) 了，\(f(i,j)\) 表示左侧 dp 到 \(i\)，钦定 \(j\) 个赢的方案数，\(g(i,j)\) 表示右侧 dp 到 \(i\)，钦定 \(j\) 个输的方案数。

然后考虑枚举 \(k\) 个赢，那么就是把 \(f(p,l)\times g(p+1,r)\to ans_{l+n-p-r}\)。其中 \(p\) 是任一满足 \(a_p<b_{k+1}\land a_{p+1}>b_k\) 的位置。

复杂度 \(O(n^2+q)\)。

省集 0705 B trans

考虑一个分治，假设当前对 \(n\times n\) 矩阵进行转置，那么递归到 \(4\) 个 \(\frac{n}{2}\times \frac{n}{2}\) 的子问题求解，然后再把左下右上进行交换。

这东西看起来是 \(T(n)=4T(\frac{n}{2})+O(n)=O(n^2)\) 的，但是我们注意到，交换左下右上的操作，对于同一层（\(n\) 相同的子问题），是可以并行进行的。

所以其实是 \(T(n)=2T(\frac{n}{2})+O(n)=O(n\log n)\)。

然后考虑如果直接这样做，我们每次要对错位的两行进行交换，最优步骤需要 \(6\) 步：对齐，\(4\) 步交换，然后再对齐。这样做是 \(3n\log n+O(n)\) 次操作。

但是题目卡的比较死，我们只能有 \(2n\log n+O(n)\) 次操作，

注意到，如果没有两步对齐，我们就可以做到 \(2n\log n\) 级别了，所以我们考虑如何每次操作“自动”对齐。

考虑第一步操作，相邻的两行要对齐，第二行要 \(\texttt{shift }1\)，第二步操作，距离 \(2\) 的两行要对齐，底下那行要 \(\texttt{shift }2\)，所以我们只要对第 \(i\) 行 \(\texttt{shift }i\)，这样每次操作就对齐了！

算上预处理取位器，总操作次数 \([n-1+2m(m-1)]+2(n-1)+2nm\)，其中 \(m=\log n\)。

省集 0705 C divisors

神仙思路。

考虑按位确定答案？？

假设当前已知 \(x\equiv v\pmod{2^k}\)，现在要确定 \(2^{k+1}\)。

考虑枚举 \(v\) 的第 \(k+1\) 位是多少。

如果是 \(0\)，那么 \(\text{Ask}(2^k-v)\) 判断返回值 \(\bmod (k+1)\) 是否为 \(0\)。

如果第 \(k+1\) 位为 \(1\)，那么 \(\text{Ask}(2^k+2^k-v)\) 判断返回值 \(\bmod (k+1)\) 是否为 \(0\)。

但是返回值为 \(0\) 只是合法的必要条件，并不是充分的，虽然搜到最后仍然合法意味着找到答案。但是这样做的复杂度？

是对的。。

省集 0706 B path / HT-NOI-? 游乐园

注意到随着起点的移动，每个点在最短路上的父亲是单调的。

然后注意到每个点最多有四种可能的父亲，所以考虑比较暴力的做法：

考虑当前处理区间 \([l,r]\)，设起点为 \(i\) 时，\(j\) 的父亲是 \(fa_i(j)\)。如果 \(fa_l(j)=fa_r(j)\)，那么意味着 \(j-fa_l(j)\) 这条边在这个区间里不变，所以考虑直接合并，然后分治递归。

细节比较多，比如合并时，要更新连向这个点的边的权值，要加上这个点到根的距离。

注意到如果某一层没有合并，那么意味着递归下去的区间里每个点的父亲只有更少的取值。

复杂度一看就是 \(O(n\log n)\) 的。

CF

CF2129

CF2129 A

\(f(S)_{\max}\) 就是线段并，\(g(S)_{\min}=0\)。考虑能不能同时取到。

考虑出现简单环的必要条件是存在两条 \([l_1,r],[l_2,r]\) 线段被选中。

然后注意到，选取子集使得线段并不变的时候，通过简单贪心，可以保证不出现这种情况，然后就做完了。

CF2129 B

考虑对于 \(p_i<p_j\)，\(p_j\) 的操作不会影响这个式子是否成立，只和 \(p_i\) 有关，所以从小到大贪心做完了。

CF2129 C1/2/3

考虑分组确定答案。首先找到一个右括号，可以简单二分找到。

然后按照 \(B\) 个一组确定答案，最简单的想法就是，如果第 \(k\) 个字符是左括号，那么匹配数加上 \(2^k\)，这样可以判断出来。

然后瞎构造一通就好了。

CF2129 D

考虑找到一个区间最大的数，以此做 dp。

令 \(f(l,r,x,y)\) 表示区间内向 \(l-1\) 贡献 \(x\)，向 \(r+1\) 贡献 \(y\) 的方案数。

转移枚举 \(k,x',y'\)，有

\[f(l,k-1,x,y')f(k+1,r,x',y)\binom{r-l}{k-l}\to f(l,r,x+dx,y+dy) \]

然后 \(dx,dy\) 就是 \(k\) 要向哪一侧贡献。注意边界 \(l=1\) 还有 \(r=n\) 的特判。

注意到一个位置最多被贡献 \(O(\log n)\) 次，所以 \(x,y\) 是这个级别的。

复杂度 \(O(n^3\log^4 n)\)。

CF2129 E

考虑莫队。但是莫队复杂度均摊，所以分块需要按照 \({\color{red}\max(1,}\deg_i{\color{red})}\) 为权值进行分块。

然后需要一个 \(O(1)-O(\sqrt n)\) 单点修改全局 \(k\) 大的值域分块。

复杂度 \((n+m+q)\sqrt{n+m}\)。

CF2129 F1

首先显然可以通过给每个位置分配不同的在查询中出现的方式，来区分答案。

通过计算，我们发现，使用 \(\binom{30}{1}\) 个出现一次的，\(\binom{30}{2}\) 个出现两次的，\(380\) 个出现三次，恰好需要 \(300+29\times 30=2040\) 个位置。

然后手摸一段时间就能找到一个分配方式。

CFdiv2CD

CF2124C

首先我们划分出所有极长不降段，两段 \((l_1,r_1)(l_2=r_1+1,r_2)\) 之间一定有 \(a_{r_1}>a_{l_2}\)，所以首先要对所有 \(a_{l_2}\) 做操作，故：

答案一定是 \(\text{lcm}_{i=1}^{n-1}\dfrac{\text{lcm}(a_i,a_{i+1})}{a_{i+1}}\) 的倍数。

然后我们注意到，需要更改的值一定是每个不降段的前缀，所以答案变大只会让这个前缀变长，一定更劣。

因为保证有解，所以直接输出。

CF2124D

要读对题目

然后注意到全局排名 \(\geq k\) 的一定可以被删除。我们把数分成

不可能被删除的，即所有数排名 \(<k\)
可以被删除的，即这些数中存在排名为 \(k\) 的。
一定被删除的，排名 \(>k\)

我们只关心可能被删除的数最多可以保留多少个，然后贪心做。

CF2112C

简单题。枚举最小的两个，然后对手有两种最优的选择，最大的取值会被限定为一个区间，因为单调，双指针做到 \(O(n^2)\)。

CF2112D

首先考虑 \(n-1\) 是简单的，只要黑白染色，每条边由黑到白即可。

考虑如果有二度点，那么构造是简单的，我们强制让这个二度点的左右分别是黑白的，然后不考虑这个二度点进行黑白染色，最后连边黑->二度点->白即可。

如果没有二度点则无解。

CF2120C

考虑最小可能构造出的是 \(n\)，最大的是 \(\frac{n(n+1)}{2}\)。

我们猜测这中间的都可以构造。

考虑如下构造：\(\forall k\in [n,\frac{n(n+1)}{2}]\)，我们一定可以选出一个集合 \(S\subseteq [2,n]\)，使得 \(\sum_{i\in S}(i-1)=k-n\)。

这个的意义是，我们把不在 \(S\) 中的数挂在 \(1\) 下面，其他从大到小连成一条链，这样这棵树的答案就是 \(k\)。

于是构造好了。

CF2120D

鸽巢原理。

先考虑行最小，显然至少要有一种颜色出现 \(a\) 次，所以 \(n_{\min}=(a-1)k+1\)。

然后考虑列最小，对于一行，会有 \(\binom{n}{a}\) 种出现情况，一共 \(k\) 中颜色，要出现 \(b\) 次，所以答案是 \(\binom{n}{a}k(b-1)+1\)。

CF

CF2122C

考虑 \(x\) 方向的最优情况，四个点 \(a,b,c,d\) 按照 \(x\) 排序，当配对有交或包含的时候即为最优，即 \((ac,bd)\) 或 \((ad,bc)\)。

需要注意到两维可以同时取到最优情况

然后注意到我们只要让 \(x\) 前一半大后一半大配对就行，\(y\) 同理。

所以只要按照 \(x\) 分两半，\(y\) 逆序配对就可以了。

CF2122D

需要注意到答案 \(O(n)\) 级别，然后随便 dp 做完了。

CF2122E

从前往后 dp 考虑最紧的限制就可以了，具体的，令 \(c_i=a_{0,i+1}-a_{1,i}\)，如果存在区间 \([l,r]\)，使得 \(c_l<0\) 并且 \(\sum_{i=l}^r c_i>0\)，就不合法。

显然最紧的限制就是最后一个 \(c<0\) 的位置为 \(l\) 的情况。

所以 \(f(i,j)\) 表示 dp 到 \(i\)，最紧的限制当前 \(\sum c_k=-j\)，然后枚举 \(-k\leq c_i\leq j\)，需要注意一开始可以存在一段 \(c\) 为正的前缀。

可以套一个前缀和优化。

CF2119C

注意到要求字典序最小，我们在前 \(n-2\) 个位置放上 \(l\)，最后两个位置：

如果 \(n\) 为奇数，直接放 \(l\)。
如果 \(n\) 为偶数，意味着每一位要求有偶数个 \(1\)，所以要放上一个 \(x\) 使得 \(x\text{ and }l=0\)，显然最小的 \(x\) 就是 \(2^{\lfloor\log_2(l)\rfloor+1}\)。如果 \(x>r\) 则无解。因为这意味着无论怎么放，每个数的最高位都一样，\(\text{xor}=0\) 而 \(\text{and}=1\)。

注意特判 \(n=2\)。

CF2119D

从前到后考虑，确定每个位置是否会被删除，如果会被删除，那么提前计算 \(a\) 的方案数，即贡献提前计算。

分几类讨论：

\(i\) 被 \([a_i,i]\) 选中
\(i\) 没有被 \([a_i,i]\) 选中：
- \(a_i=0\)
  - 后面也没有选中 \(i\)
  - 后面选中了 \(i\)，贡献提前计算。
- \(a_i\neq 0\)，删除前面钦定将被删除的某个数
  - 后面也没有选中 \(i\)
  - 后面选中了 \(i\)，贡献提前计算。

然后直接 dp，\(f(i,j)\) 表示 dp 到第 \(i\) 个数，前面有 \(j\) 个将被删除的数，的方案数。

答案即为 \(f(n,0)\)。

CF715E

考虑 \(p_i\to q_i\) 连边形成置换环，答案就是 \(n-c\)，其中 \(c\) 为置换环个数。

然后设未知为 \(0\)。

把 \(x\to y,x\neq 0,y\neq 0\) 两侧的 \(x,y\) 缩起来。

如果（在缩点后）出现了 \(0\to x,x\to 0\)，那么变为 \(0\to 0\)。

那么现在我们有 \(x\to x, 0\to x, x\to 0, 0\to 0\)。

把 \(x\to x\) 这种扔掉，算作一个置换环，设一共有 \(c\) 个。最后考虑。

考虑合并顺序。

因为 \(0\to x,x\to 0\) 和自己合并是封闭的，\(0\to x,x\to 0\) 和 \(0\to 0\) 合并得到 \(0\to 0\)。

所以按照 \(0\to x\) 与其他合并，\(x\to 0\) 与其他合并，\(0\to 0\) 合并的顺序考虑。

然后考虑 \(0\to x\) 怎么去到一个环中。有：

\(0\to x,0\to y \Rightarrow 0\to y\)。
\(0\to x,0\to 0 \Rightarrow 0\to 0\)。

我们先选定 \(i\) 个 \(0\to x\) 自己合并成 \(j\) 个环，则方案数是：

\(f(j)=\sum_{i=0}^{cnt0x}\binom{cnt0x}{i}\begin{bmatrix}i\\j\end{bmatrix}(cnt0x-i+cnt00-1)^{\underline{cnt0x-i}}\)

里面的下降幂是指，一个 \(0\to x\) 可以选择：

接到当前任何一个 \(0\to y\) 中（\(0\to y,0\to x\Rightarrow 0\to x\)）
任何一个 \(0\to 0\) 中。（\(0\to x,0\to 0\Rightarrow 0\to 0\)）

注意第二个的实际意义是填入 \(x\)，第一个的实际意义是填入 \(y\)。

所以每次操作会少一条边，操作方案数只和当前操作了几次有关。所以就是一个下降幂。

设 \(x\to 0\) 的方案数是 \(g\)，同理。

然后考虑 \(0\to 0\) 的方案数。

考虑会构成 \(j\) 个环，则：

\(h(j)=cnt00!\begin{bmatrix}cnt00\\j\end{bmatrix}\)

因为 \(0\to 0\) 可以任意标号，所以记得乘上阶乘。

然后卷积一下就好了。设 \(F=f\times g\times h\)。

则 \(ans_{i+c}=F(n-i)\)。

AT

ARC 202

ARC202A

肯定是从最小的开始让他升高。因为一段相同的数分开存不好决策合并方案，所以需要并起来存。

ARC202B

在 \(m\) 是奇数的时候，第一轮的方向决定了后面所有轮的方向。

在 \(m\) 是偶数的时候，前两轮的方向决定了后面所有轮的方向。

所以我们只要简单组合数算出第一轮就行了。

ARC202C

注意到 \(\gcd(R_x,R_y)=R_{\gcd(x,y)}\)，但是 \(\text{lcm}\) 没有很好的性质。

所以做 \(\gcd-\text{lcm}\) 容斥，\(\text{lcm}(U)=\prod_{S\subseteq U}\gcd(S)^{(-1)^{|S|-1}}\)。

我们要维护当前 \([1,k]\) 前缀，\(gcd(S)=j\) 的 \(S\) 的个数有 \(b_j\) 个，并快速增量更新即可。

维护 \(c_x\) 表示 \(\sum_{x|i}b_i\) 以支持快速查询，注意到一个 \(a_i\) 只会更新 \(d(a_i)\) 个 \(b\)，更新 \(O(d^2)\) 个 \(c\)。

注意到当 \(a\) 不同时，均摊每次是 \(O(\log^2 n+\log n\log \bmod)\) 的。

ARC202D

考虑拆成两维分别做。

但是可能会出现两维都钦定某次操作不移动导致实际操作次数少，所以需要施以二项式反演，把计数恰好转为计数最多。

考虑一维带限制的游走，使用反射容斥，然后做到 \(O(\frac{t^2}{n})\)，然后根号分治：

对于 \(n<B\)，直接 dp 做到 \(O(tB)\)。
对于 \(n\geq B\)，反射容斥做到 \(O(\frac{t^2}{B})\)。

平衡可得 \(O(n^{1.5})\)。

此时得到一维操作次数为 \(n\) 的方案数 \(h(n)\)，然后两维合并，得到不超过 \(k\) 次操作的方案数 \(g(k)=\sum_{i=0}^kh(i)\binom{k}{i}\)，拆一下组合数直接卷积做到 \(O(n\log n)\)。

然后再二项式反演一下即得最终答案。

MX-BJ-A 题单

AGC008E

考虑 \(a\) 是一个基环树。

考虑只有一个环的基环树连通块，分类讨论：

可以把两个长度相同的环合并起来
一个奇环可以有两种构造 \(p\) 的方式。

对于一般的基环树：

考虑多出来的只能是一段链，然后按顺序插入，有 0/1/2 种可能。

AGC030D

考虑一共 \(n^2\) 条边，那么暴力记录每对 \((i,j)\) 有多少概率满足 \(p_i>p_j\)。

然后注意到交换 \(x,y\) 只会影响 \(f(x/y,*)f(*,x/y)\)，然后 \(O(n)\) 暴力更新被影响的就好了。

复杂度 \(O((n+q)n)\)。

AGC030C

考虑正着放 \(k\) 种颜色，但是添加颜色很困难。

考虑斜着放。斜着放 \(k\) 种颜色，\((i,j)\) 放 \((i+j)\bmod k\)，考虑添加颜色，我们发现，可以选择某种颜色，然后按照 \(i\) 的奇偶性更改颜色，这样可以构造出 \([k,2k]\) 种的颜色个数。然后做完了。

AGC005E

神人题目

考虑如果存在 \(x\) 树的一条边使得两端点在 \(y\) 树的距离 \(>2\)，那么只要走到这条边就可以输出 -1。

所以考虑能不能走到。

注意到如果只有在 \(y\) 中距离 \(\leq 2\) 的边，那么 \(x\) 不可能跳过 \(y\) 到达其父亲，因为下一步就会被 \(y\) 吃掉。

所以问题变成，\(x\) 第 \(i\) 步不能走 \(S_i\) 中的点，问 \(x\) 可以走几步。

简单 dfs 即可。

AGC009D / P5912 / [241116] 树的顶点标号

考虑答案上界就是点分树，答案一定不超过 \(O(\log n)\)。

考虑贪心。

随机选择一个根，然后递归下去，得到每个子树有哪些标号还没有被覆盖，然后找到合法的第一个，填上即可。

复杂度 \(O(n\log n)\)。

QOJ

MX-BJ-A 题单（集训队互测 2022-2023）

QOJ 5013

QOJ 5015

luogu

杂题

P1220

有简单 \(O(n^2)\) 区间 dp。

考虑更优秀的做法。

我们考虑我们按照折返点顺序 dp。我们考虑贡献提前，考虑 \(f(i)\) 表示 dp 到的最后一个折返点是 \(i\)，会让答案至少多出多少。

什么是至少多出多少呢？我们考虑，无论下一个折返点是什么，再次到达第 \(j\) 个路灯的时间 \(\geq\) 当前时间加上 \(|a_j-a_i|\)。

所以我们只考虑超出这个时间的代价。

我们发现，这样选择下一个折返点的代价只和 \(i,f(i)\) 有关系。

同时答案就是 \(\min(f(1),f(n))\)。

考虑转移的贡献，这里给出式子：

对于 \(i<c<j\)，有：

\(f(j)=W(i)\times 2(a_j-a_i)+f(i)\)。其中 \(W(i)=\sum_{i=1}^{\red{i-1}}w_i\)

\(j<c<i\) 同理。

这个转移的代价可以这么理解：从 \(i\to j\)，\(\geq i\) 的部分仍然可以（已经）取到了最小代价，只有 \(<i\) 的部分的最小代价加上了来回的时间 \(2(a_j-a_i)\)。

注意到左右两侧转移是交叉的，并且转移后代价更大，所以我们考虑从 \([c,c]\) 开始，挑答案小的部分扩展。

然后注意到转移可以写成斜率优化，同时 \(W(i)\) 是单调的，使用单调队列维护直线，这样做到 \(O(n)\)。

P10818

Raney 引理：

对于一个序列 \(x\)，如果满足 \(\sum_{i=1}^nx_i=1\)，则 \(x\) 的循环同构序列中有且仅有一个满足前缀和都是正数。

考虑这道题，需要找到所有满足要求的序列使得前缀和是正的。满足 \(\sum x=0\)。

考虑 Raney 需要 \(\sum x=1\)，所以考虑给最后加一个 \(-1\)，然后所有项取反并倒置。

这样满足要求的条件就和 Raney 一样了。

然后考虑一共 \((m+1)!/(m+1)=m!\) 种圆排列，然后注意到需要去掉一开始加的 \(-1\)，但是每个 \(-1\) 无法区分，所以需要除掉 \(m-n+1\)。

答案就是 \(\frac{m!}{m-n+1}\)。

容斥题单

P1316

考虑求出现了 \(k\) 次的情况有几次，记为 \(g(k)\)，那么答案就是 \(\frac{n(n+1)}{2}m^n-\sum_{i>0}(i-1)g(i)\)。

因为 \(n\) 非常小，所以我们考虑直接 \(2^n\) 枚举串的出现位置，然后枚举串长计算方案数。这部分 \(O(2^nn^2)\)。

设 \(h(S)\) 为出现集合为 \(S\) 的方案数。

注意到这样求，每种方案的出现子集都会被算一遍，所以要施以子集容斥，即 \(f(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}h(T)\)。

直接做是 \(O(3^n)\) 的，但是使用 SOS dp 做到 \(O(n2^n)\)。

P2714

套路题。考虑若 \(\forall i\in S,d|i\)，则 \(d|\gcd(S)\)。

故枚举 \(d\)，得到 \(h(d)=\sum_{S}[d|\gcd(S)]\)，这里简单组合数就可以得到。

然后再倍数容斥一下，\(h(n)=\sum_{n|m}f(m)\Leftrightarrow f(n)=\sum_{n|m}g(m)\mu(m/n)\)。

当然有更简单的做法就是递推，从大到小递推：\(f(n)=h(n)-\sum_{m>n,n|m}f(m)\)。

复杂度 \(O(Tv\log v)\)。

P2992

考虑我们枚举一个顶点 \(A\)，那么构成合法三角的必要条件是，另外两个点 \(B,C\) 在 \(OA\) 两侧。

考虑一个合法三角 \(ABC\)，会在每个点都被统计一次，但是不合法三角，只会恰好在一个点被统计一次。

所以我们按这个方法统计，然后减去所有情况，得到的答案 \(/2\) 即可。

P3158

因为不同颜色棋子不能在同一行同一列，所以我们单独考虑每种颜色棋子占用了几行几列，然后背包合并。

和前面类似，直接对每种颜色容斥出恰好占用 \(n\) 行 \(m\) 列的方案数 \(f(n,m)\)。

然后 \(g(n,m)\) 表示一共占用了 \(n\) 行 \(m\) 列，有 \(g_0(a,b)f(c,d)\binom{a}{c}\binom{b}{d}\to g(a+c,b+d)\)。

然后答案就是 \(\sum g(a,b)\binom{n}{a}\binom{m}{b}\)。

P3160

设要求的局部最小集合为 \(A\)。

首先恰好只有 \(S\) 中是局部最小比较难算，比较好算的是 \(S\) 的超集是局部最小的方案数。

注意到，若我们钦定 \(S\)，那么 可以从小到大填数的时候，维护已经被填的 \(S\) 中的位置，然后直接做状压 dp。

那么我们直接枚举可能有贡献的 \(S\)，大约 \(10^4\) 个，然后对这些分别做 dp，然后容斥一下求出答案即可。答案是 \(\sum_{A\subseteq S}(-1)^{|S|-|A|}f(S)\)。

P2595

考虑钦定某行某列一定有跨越的骨牌比较困难，我们 考虑容斥，变成没有某行某列没有跨越的牌。

那么我们对行集合 \(L\)，列集合 \(R\) 分别容斥，也就是钦定 \(L\) 中无跨越，\(R\) 中无跨越，那么答案就是 \(\sum_{L,R}(-1)^{|L|+|R|}f(L,R)\)。复杂度是 \(O(2^{n+m})\)，比较爆炸。

考虑当我们钦定了 \(L\)，\(R\) 不需要那么暴力，我们只要考虑求出在满足行限制的情况下：

\(g(n)\) 表示前 \(n\) 列没有无跨越的方案数。
\(h(l,r)\) 表示只考虑 \([l,r]\) 列，所有填牌的方案数。

那么可以递推，有 \(g(n)=h(1,n)-\sum_k g(k)h(k+1,n)\)。

我们只要先 \(O(2^nn^3)\) 预处理出 \(w(xl,xr,yl,yr)\) 表示这个矩形区域中，不考虑行列限制的填法数量，然后 \(h\) 是好处理的，自然 \(g\) 也是好算的。

这样总复杂度 \(O(2^nn^3)\)。

斯特林数相关

P4091

考虑把 \(S(i,j)\) 变为通项形式，即 \(S(i,j)=\sum_{k=0}^j\frac{(-1)^{j-k}k^i}{k!(j-k)!}\)。

注意这个通项对 \(j>i\) 仍然有效。

然后带入原式一顿变化，变成：

\[\sum_{j=0}^n2^jj!\sum_{k=0}^j(-1)^{j-k}\frac{1}{(j-k)!}\left(\sum_{i=0}^nk^i\right)\frac{1}{k!} \]

我们注意到令 \(f(i)=\frac{(-1)^i}{i!},g(i)=\left(\sum_{j=0}^ni^j\right)\frac{1}{i!}\)。

令 \(h=f\times g\)，则原式即为 \(\sum_{j=0}^n2^jj!h(j)\)。

故一次 NTT 解决。

P4827

如果暴力记录 \(f(i,c)=\sum_jdis(i,j)^c\)，\(f(i,c)\) 的转移和 \(f(x,c'\leq c)\) 有关，复杂度是 \(O(nk^2)\) 的。

考虑把 \(dis(i,j)^k\) 拆成 \(\sum_{c=0}^kS(k,c)\binom{dis(i,j)}{c}c!\)

然后注意到我们只需要记录 \(f(i,c)=\sum_j \binom{dis(i,j)}{c}\) 即可，转移只和 \(f(x,c),f(x,c-1)\) 有关。复杂度 \(O(nk)\)。

P6667

考虑 \(f(x)=\sum_{i=0}^m\binom{x}{i}s_i\)。

直接带入瞎算一通就好了。

问题是如何求 \(s_i\)。二项式反演得到 \(s_i\) 和 \(f(x)\) 的关系，然后使用 NTT 做完了。

单位根反演相关

其实就是 \([k|n]=\sum_{i=0}^{k-1} \omega_{k}^{in}\)。

P5293

先不考虑 \(L\)，那么有 \(g(n)\) 表示若已知每步在哪一列，走了 \(n\) 步的方案数。

显然有矩阵加速转移。初始矩阵 \(A\) 中 \(A[0][x]=1\)。转移矩阵 \(B=W\)。

则 \(g(n)=AB^n\)（的第 \(y\) 个元素，后面略去）。

然后考虑 \(L\)，设 \(f(n)\) 表示网格走了 \(n\) 步的方案数。则 \(f(n)=\binom{L}{n}g(n)\)。

然后 \(ans_t=\sum_{i=0}^L[i\bmod k=t]f(i)\)。

然后大力推式子：

\[\begin{aligned} ans_t&=\sum_{i=0}^L[i\bmod k=t]f(i)\\ &=\sum_{i=0}^L[k|(i-t)]f(i)\\ &=\sum_{i=0}^L\sum_{j=0}^{k-1}\frac{1}{k}\omega_{k}^{j(i-t)}\binom{L}{i}AB^i\\ &=\sum_{j=0}^{k-1}\frac{1}{k}\omega_{k}^{-tj}A\sum_{i=0}^L\omega_{k}^{ij}\binom{L}{i}B^i\\ \end{aligned} \]

这里注意，如果矩阵 \(XY=YX\)，则可以使用矩阵的二项式定理：\((X+Y)^n=\sum_{i=0}^n\binom{n}{i}X^iY^{n-i}\)。

\[\begin{aligned} ans_t&=\sum_{j=0}^{k-1}\frac{1}{k}\omega_{k}^{-tj}A(\omega_{k}^{j}B+I)^L\\ &=\sum_{j=0}^{k-1}\frac{1}{k}\omega_{k}^{\binom{j}{2}+\binom{t}{2}-\binom{j+t}{2}}A(\omega_{k}^{j}B+I)^L\\ k\times ans_t\omega_k^{-\binom{t}{2}}&=\sum_{j=0}^{k-1}[\omega_{k}^{\binom{j}{2}}A(\omega_{k}^{j}B+I)^L][\omega_{k}^{-\binom{j+t}{2}}]\\ \end{aligned} \]

然后发现这是一个卷积的形式，然后上 MTT 就好了。

P10664

会了 P5293，这道就是简单题。

P5591

只要注意，\(\lfloor\frac{i}{k}\rfloor\) 比较好的拆法是：\(\frac{1}{k}(i-i\bmod k)\)。

然后无脑推推推就好了。

chirp-Z 变换

已知 \(P\)，求 \(P(1),P(c),\cdots,P(c^k)\)。

只要知道 \(ij=\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}\)，然后硬拆就好了。

用处是做任意长度卷积？

MX-BJ-A

Day 1

福建省队集训 Day 1。

Day 2

T1 / Gym-104337B mode

神秘数位 dp。考虑答案等于 \(K(r-l+1)-\sum_{i=0}^{K-1}\sum_{i=l}^r[f(i)\leq i]\)。其中 \(K\) 是最大位数。

然后就变成限定每个数出现次数，计数 \([l,r]\) 里面有多少满足要求的数。简单背包之类就做完了。

复杂度 \(O(TK^4B)\)。其中 \(B=10\) 表示进制。

T2 / P7154

dp 数数题。

考虑找到一个答案的唯一特征，使得可以补充不漏计数。

发现我们找到第一个 \(A\) 未匹配的 \(x\)，那么对于 \(a_i>x\) 都必须成功匹配。

然后枚举 \(x\)，两侧拼起来计数就好了。

T3 / P8276

首先注意到，对于出度为 \(1\) 的，可以把其和出边对应的点合并起来，然后我们大胆猜测可以不断这样操作，最后判定两个点是否被并起来。

但是需要注意到的一点是，不能真的合并，而是染色判定是否出边颜色唯一，如果唯一则被染色。

Day 3

T1

注意到最短路的势能是 \(O(m2^m)\) 的，所以直接暴力单点更新，复杂度是 \(O(m^22^m)\) 的。

T2 / P10818

注意到 rnd 每次只有位的异或运算，所以拆位，对于每一位看做未知数，建立异或方程组，对于第 \(i\) 个限制，我们可以得到满足 \(2^k|i\) 的关于第 \(k\) 位的方程。

当 \(n=50\) 时，可以得到 \(47\) 个方程，这样有 \(k=17\) 个未知数。直接 \(O(2^k)\) 枚举。

T3 / CF1210F2 加强版

原题 \(n\leq 7\) 做法：考虑逐次加入右部点，维护左部点和已经加入的右部点所有的匹配方式并压入状态，这样乍一看复杂度很爆，但是经过搜索，只有大约 \(7\times 10^4\) 种状态。

于是直接 dp 就做完了。本质上是 dp of dp。

\(n\leq 9\) 考虑使用 Hall 定理，注意到 Hall 定理要求所有子集满足，所以我们对不满足进行计数。

我们考虑需要对每个不满足情况找到代表子集。

考虑找 \(S\),使得 \(|S|-|N(S)|\) 最大，在此基础上 \(|S|\) 最小。

可以证明，如果存在 \(T\) 和 \(S\) 在这些条件上相同，那么 \(S\cap T\) 或 \(S\cup T\) 某一个一定更优秀。

然后一开始就考虑全局比较难，考虑 \(f(S,NS)\) 表示左右部点是 \(S,NS\) 时，\(S\) 是其代表子集的概率。

设 \(g(S,NS)\) 表示左右部点是 \(S,NS\) 时，图有完美匹配的概率。

然后设两个辅助数组 \(h(S,T)\) 表示 \(T\) 中每个点在 \(S\) 中至少有一条边的概率。

\(w(S,T)\) 表示没有边的概率。

于是通过枚举 \(S,NS\)，我们有：

\(|S|<|NS|\)，\(f(S,NS)=h(S,NS)-\sum\limits_{T\subseteq S,NT\subseteq NS}f(T,NT)w(T,NS-NT)g(S-T,NS-NT)\)。
\(|S|\geq |NS|\)，\(g(S,NS)=h(S,NS)-\sum\limits_{T\subseteq S,NT\subseteq NS}f(T,NT)w(T,NS-NT)g(S-T,NS-NT)\)。

这里就是保证：