About Me

在无数久的 🐦咕咕咕 后一个新博客它建成了！

终于做了一些比 入门篇 难一些的题。

A AUOJ1600 礼物

其实是道板子+式子题。大概是 Burnside 引理的第一种题型（强行拼上去）。

我们考虑设 $f(a,b)$ 为 $a$ 个点形成环，从中选择 $b$ 个位置选中，且选中位置没有连续 $k$ 个的方案数量。

由于是循环同构，我们枚举置换再算环的个数，然后就可以得到和入门篇基本一样的式子，然后最后就是：

$\sum_{i | n,i | m} f(\frac n i ,\frac m i) \varphi(i)$

考虑怎么快速计算 $f(a,b)$ 。

B Parades

这题有一个关键的性质：可以发现一定有一种全局最优解满足每个点都是局部最优解。具体来说，由于每个点向上只有一条边，所以即使你在这个点子树的时候放弃选择一条路径，也只能最多获得 $1$ 的贡献，还不如直接选择子树之内。（感觉这种性质在权值全 $1$ 的时候都可以尝试一下有没有）

于是我们设 $dp[u]$ 表示 $u$ 子树最多可以选多少个路径，再对每个子树维护出一个集合，这个集合中的点满足存在一个选择最多路径的方案，使得这个点没有被覆盖。

考虑转移，由于 $n \le 10^3$ 且度数很小，我们可以在每个点做一个状压，转移出当连向某些儿子的边被选择时，最多可以选择多少个路径（感觉可能这个东西也是可以流的）。然后把所有取到最大值的状态取个交，得到的集合就是如果想要获得最大值就必须放弃的子树，剩下的子树都是存在方案使得不被覆盖的，由于最多只会选一条路径连上去，所以这么做是对的。

复杂度 $O(\frac{n^2}{\omega} + nd^22^d)$ 。

A (False) faces

题解在 这里 。

B Pachinko

我们考虑设出 $s_{i,j}$ 表示经过 $s_{i,j}$ 的期望次数。那么可以对每个格子列出一个方程。由于每个 T 位置不会往外走，也就是说走到这个点就结束了，所以期望次数可以直接看成一个概率，最后除以会结束的总概率即可。但是直接进行高斯消元是 $O(n^3m^3)$ 的，无法接受。

然后会发现这个矩阵非常有性质。由于这个矩阵是 $n \times m,10^4 \times 20$ 的，而一个位置的方程仅在 $[i-m,i+m]$ 有值。因此高斯消元的时候，每一行只会影响到后面 $m$ 行。

但是还有一个问题，在进行交换的时候，显然只需要尝试把后 $m$ 行交换过来，交换过来后就可能影响 $[i+1,i+2m]$ 的系数了。因此需要对每个位置存储 $[i-m,i+2m]$ 的系数。记得在交换后需要改变这个方程可能有值的区间，由于 $i$ 前面都是 $0$ ，这个改变只可能是前面砍掉一些 $0$ 后面加上一些 $0$ 。

复杂度 $O(nm^3)$ 。

A Yet Another LCP Problem

考虑反过来看串，如果建立前缀树，会发现这个 LCP 长度的问题就可以看成对于所有一类集合的点都到根全部 +1 ，对所有二类集合点求和。但是由于一般来说前缀树显然是建不出来的只能建出 parent 树，而如果建出 parent 树后，相当于这个点父亲到根的所有串全部 +1 ，然后需要特殊处理当前点。因此树剖显得挺难受，于是考虑建立虚树后 dfs 两遍做即可。细节可以参考代码。

复杂度 $O(n\log n)$ 对每个点上串的长度需要排序，以及建虚树时需要排序。

Light switches

注意到 $S \le 30$ ，我们考虑进行折半搜索。考虑复杂度是啥，如果所有集合操作都使用 bitset ，不难发现这里的两个开关并起来就是做个异或，那么考虑枚举一下前 $A$ 个开关的情况进行预处理，然后查询的时候对剩下的开关枚举情况，预处理的东西丢进一个 unordered_map 里（貌似 unordered_map 对 bitset 有自带的 Hash 方式），复杂度就是 $O(2^A \frac Nw + q\frac N w 2^{S-A})$ ，不难发现在 $A$ 大概取到 $20$ 的时候，运算次数大概是 $\frac{10^9}{32}$ 左右，非常稳。

一个我没写过的套路。

这个题目其实就是问你给你一个串，可以往前添加一些字符，往后添加一些字符，有多少种添加方式使得最终串不同。

我们先考虑向前添加字符，不难发现一个字符串向前添加字符可以得到的就是 parent 树子树内的本质不同的所有字符串。设这个串长为 $|S|$ ，子树内的本质不同串的个数为 $a$ ，当前点上最短串长为 $b$ ，那么添加方案数就是 $a+b-|S|$ 。

我们按照与对角线平行的线上的数来考虑。如果只考虑在一条这样的对角线上进行操作，那么就变成了一个普通的 Nim 游戏。而如果有很多对角线，不难发现在进行一次操作的时候，这个人可以把后面的所有对角线的状态改变。

于是我们考虑找出第一个异或和不为 $0$ 的对角线，这个对角线单看是先手必胜的。考虑先手对这个对角线进行一次操作把它的异或值变为 $0$ 。要么此时已经没有数了，先手胜利。要么后手会有一些选项：选择这条对角线或之前的对角线，这样的话必然会导致一条对角线的异或和变成非 $0$ ，先手可以继续操作。否则他会去选择这条对角线后面的对角线。但是后面的对角线可以由先手这一轮操作一下，使得后面的所有对角线的异或和都为 $0$ ，于是后手就没办法了。

于是就可以得出结论：后手必胜当且仅当所有对角线的异或和为 $0$ 。

首先，模 $2$ 就是行列式的值。

我们考虑容斥，钦定某些列没有数被选，那么有

$\text{perm } A = (-1)^n \sum_{x \in \{0,1\}^n} (-1)^{x_1+x_2+\cdots +x_n} \prod _{i=1}^n (Ax)_i$

也就是钦定某些列不选，然后每一行任意选一个数。

由于后面有一个 $\prod$ ，也就是说一个 $x$ 会造成贡献当且仅当 $Ax$ 中 $0$ 的个数小于等于 $1$ 。

A Winding polygonal line

神仙构造。

考虑拿凸包上一个点 $A$ ，然后每次找一个点 $B$ ，如果是 L ，则使得剩下的所有点都在 $AB$ 的左侧，然后连过去即可，否则就使得所有点都在 $AB$ 右侧。不难发现这样每一轮都一定能找到剩余点继续，且由于所有点都在一侧，显然不可能出现线段相交。

复杂度 $O(n^2)$ 。

B Distinctification

考虑给定一段序列怎么算出答案。不难发现对于一个 $A_i$ ，我们一定会找到一个最大的 $k$ 满足 $[A_i,A_i+k-1]$ 的数的个数正好是 $k$ ，然后把这些数进行操作使得这些数互不相同。

我们定义一个方案的权值为 $\sum_i A_iB_i$ ，那么最终需要花费的代价是 $W_e - W_s$ ，而我们希望这个代价尽量小，也就是最小化最终状态的代价。而且不难发现，在题目的条件下，一定可以将 $A_i,B_i$ 变成 $k,B_i$ 其中 $k \in [A_i,A_i+k-1]$ 。具体为啥想一想就会发现这个方案非常容易构造，可以先任意得到一个每个数不同的方案，然后一个一个归位即可。

考虑对于一个数组 $a_{1,\dots ,n}$ 怎么求出答案，其中 $0$ 为根。考虑每一条边 $i \to f_i$ 的贡献，显然是 $siz_i(n+1-siz_i)$ 。那么我们可以枚举这个点的子树的 $siz$ 然后算这种情况的概率，而算概率则直接统计有多少种加边后的方案使得取到这个 $siz$ 然后除以总方案数 $n!$ 即可。考虑方案数量的计算，如果确定后面有 $s$ 个点在子树内（不包括 $i$ ），这些点的父亲的方案分别是 $1,2,3,\dots ,s$ ，因为第一个子树内的点的父亲必须是 $i$ ，第二个可以是第一个或者 $i$ …… 然后考虑这个子树之外（不包括 $i$ ）的点。这些点的方案数显然依次是 $1,2,\dots,n-s-1$ 。最后考虑 $i$ 的父亲的方案数，它可以连向 $0 \sim i-1$ ，是 $i$ ，于是式子就是：

$\frac{1}{n!}\sum_{i=1}^n A_i \sum_{s=0}^{n-i} \binom {n-i} s s!(n-s-1)!i[(s+1)(n+1)-(s+1)^2]$

为了方便，暂时不写最前面的 $\frac 1{n!}$ 了。

其实这个东西可以 OEIS 到，不过还是正经写一下吧。

考虑如何求出 $P(x)$ ，我们对它质因数分解成 $\prod p_i^{c_i}$ ，然后会发现这个东西可以对每个质因数分开考虑，最后使用 CRT 合并即可。考虑对于一个 $p_i^{c_i}$ ，它的阶是 $\varphi(p_i^{c_i}) = (p_i-1)p_i^{c_i-1}$ 。首先讨论 $p_i \ge 3$ ，设原根为 $\omega$ ，那么有 $\omega^{(p_i-1)p_i^{c_i-1}} = 1$ 。讨论一下，如果 $3 \not | (p_i - 1)p_i^{c_i-1}$ ，那么唯一的解就是 $1$ ，这个非常显然。否则，可以得到三个解，分别是原根的 $\frac 1 3 (p_i-1)p_i^{c_i-1}$ ，$\frac23 (p_i-1)p_i^{c_i-1}$ 和 $1$ 。也就是说，这种情况存在三个解的前提是 $p_i \equiv 1 \pmod 3$ 或者 $p_i = 3 , c_i > 1$ 。

有意思的题。

这个问题是有一个普遍结论的：在 $\frac n e$ 附近之前全部不管，之后就遇到一个位置为前缀最小值则直接选。

考虑这个东西是怎么来的。我们设 $f_i$ 表示 $1 \sim i-1$ 都不管，从 $i$ 开始遇到一个位置为前缀最小值则直接选择，最终得到 $1$ 的概率。

考虑如果能建立出前后缀的最小生成树，然后就只需要往里面添加开头向结尾的边的问题。

然后会发现，实际上这些边只会连接开头、结尾这 $2n$ 个点，由于断边也只会断这 $2n$ 个点中两两路径上的一些最大边，于是我们考虑维护出每个前缀和后缀的生成树上这 $n$ 个点的虚树，虚树上边权就是路径上边权的最大值。由于这样虚数点数是 $O(n)$ 的，所以甚至可以对每个前缀和后缀的虚树都存下来！

但是怎么维护这样的虚树呢？比如我们维护了 $[1,i]$ 的虚树，考虑加入 $i+1$ 这一列的点求虚树。不难发现只有第 $i$ 列点和后面加入的这一列的点有边相连，所以只需要考虑第 $i$ 列的点两两路径，于是可以干脆把这些点也给作为关键点丢进虚树里，解决这一列后再重新求一边虚树，把上一列丢掉，于是总是可以保证里面点数 $O(n)$ 。然后合并的过程或者加边的过程就是把虚树和新边拿出来做一次 kruskal 即可。

好题。首先我们考虑一天之内能到达的情况。我们考虑对于每一对 $s,t$ 求出一个最晚的时间 $T$ ，使得在 $T$ 之前的时刻出发，都可以在当天到达 $t$ （这里要注意有可能一天之内到不了，也就是可能 $T < 0$ ）。

这个东西如何计算？首先有一种非常暴力的想法，我们每次加入一个当前连通块连出去的边，同时可能导致 $T$ 减小，然后重新跑一次最短路。考虑这样的复杂度，枚举点 $O(n)$ ，加边次数是 $O(n^2)$ ，每次跑最短路使用 dijkstra （这里显然 $O(n^2+m)$ 是优于 $O(m\log m)$ 的），复杂度就是 $O(n^5)$ 。看起来不太能跑过。

考虑一个 $dp$ ，设 $dp[R][t]$ 表示在 $t$ 时刻已经解决了 $1 \sim R$ 的所有患者。考虑转移就是枚举下一个治疗计划用哪一个。设下一个治疗计划为 $(l,r,c)$ 那么分为两类：

• $c > t$ ，那么在下一次使用治疗计划的时间在现在之后，由于中间不能有剩余的患者，有 $l \le R-(c-t)$ ，也就是 $c > t,l + c \le R+t$ 。
• $c < t$ ，也就是说之前进行了一次治疗计划用来覆盖 $R$ 后的一段，那么中间没有剩余患者的条件是 $l \le R - (t-c)$ ，也就是 $l - c \le R - t$ 。

在这两种情况下，可以转移到 $dp[r][c]$ 。

一道很有意思的题，我也不知道这个题解是否写清楚了。。

设 A 是 Gennady ， B 是 Georgiy 。

首先考虑如何找出所有会使游戏无限进行下去的点。这种点分为两种，一种是从这个点，A 先手出发，就会导致最终平局，还有一种是 B 先手出发却会导致不得不平局。

首先考虑所有出度为 $0$ 的点，显然不管谁从这个点先手，游戏都会结束。

由于 A 的决策是尽量平局，所以一个点 A 出发无法平局当且仅当它的所有后继点都是 B 出发会导致不平局的情况。

从一般的求字典序最小的拓扑排序入手。考虑第一次加入无入度点后，得到了一个小根堆 $mn$ 。我们的目标是让这一次拿的是这个小根堆里面尽量大的数。先假装 $k$ 足够，于是我们把这里面除了最后一个数之外的所有数全部丢出小根堆并且维护到一个大根堆里面。然后对于最后一个数，如果它比大根堆的最大值还大，显然没有必要把它丢出去，直接用就是最优的。否则，肯定是把它也丢出去，然后拿大根堆里面的最大的出来，从拓扑序上上一次的点向这个点连边，这样一定能钦定在字典序最小的情况下，这个点的位置就在这里。

也就是说，当我们把一个数从小根堆拿到大根堆的时候，就意味着之后这个数出大根堆的时候一定会需要从拓扑序的最后一个位置向它连边，需要耗费 $1$ 的代价。

那么就有了一个做法。在小根堆直到只剩一个数前且 $k$ 足够时尽量 pop 并且丢进大根堆并更新 $k$ ，只剩一个的时候判断一下是否需要弹出。然后如果小根有东西就只能优先连小根堆的东西，且不需要加边，否则连大根堆的东西且用上次的点连向这个点。

为了做这个题学了一下支配树大概是个什么玩意。一般图支配树被鸽了，只写一下 DAG 上支配树的做法。

考虑一个单源有向图，上的一个点 $u$ 如果存在一个点 $v$ 满足删除 $v$ 后 $u$ 无法从源点到达，那么我们称 $v$ 支配点 $u$ 。

显然，同一个点的支配点很多，设这些点是 $v_1,v_2, \dots ,v_k$ ，同时显然源点也是一个支配点。

• 如果 $a$ 支配 $b$ ，$b$ 支配 $c$ ，那么有 $a$ 支配 $c$ 。证明显然。
• 如果 $a$ 支配 $c$ ，$b$ 也支配 $c$ ，那么 $a,b$ 间一定存在支配关系。如果不存在，那么显然从原点通过 $a,b$ 均可到达 $c$ ，因此这两个点就都不支配 $c$ 了。

也是道不错的题，大概是第一次做到按点权建 Kruskal 重构树。

捐赠的过程是一个经典的问题，一般的做法是倒着考虑后贪心。倒着考虑这个问题，于是变成了选择一个初始点，在任意点的时候身上的钱的数量必须不小于 $\max(A_i - B_i , 0)$ ，并且到达一个点后就可以选择获得 $B_i$ 块钱，你需要最小化最终的钱数。

为了方便，我们设 $C_i = \max(A_i - B_i , 0)$ 。如果是个完全图就可以直接按照 $C_i$ 从小到大贪心拿。但是事实上，由于具有图的限制，想要拿某个很小的 $C_i$ 需要经过一些很大的 $C_i$ 。因此可以按照点权建立出 kruskal 重构树，具体来说，令一个点的子树为这个点可以通过走小于等于这个点点权的点走到的连通块，建立的方法类似于用边建重构树，按照点权从小到大排序，然后枚举出边，找到所有相连的权值小于这个点的点，然后连向它所在连通块最靠上的点。