About Me

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

每天只挑最简单的做就是我了

称有人的点为关键点。

首先观察样例会发现，如果关键点的个数为奇数，答案肯定是 $1$ 。我们设任意一个开会地点为 $u$ ，那么显然有所有儿子子树内的关键点个数不超过一半，而又是奇数，往任何一个方向走肯定都无法使得答案保持不变，而且一定是变得不优。同时如果你一直往某个方向走，原本子树大小不超过一半之后也一定不超过，所以一定会越来越不优。

类似的思路，考虑偶数的时候，如果存在多解，肯定是找到了一个点，使得所有点被平均分配到两个子树里面，这样就可以把根向这两个子树移动，如果不是这样分配的，显然也走不动。

考虑什么样的排列可以通过 $k$ 次操作达到。不难发现当且仅当排列中存在一个区间，满足区间单增且区间长度 $\ge n - k$ 。由于存在会比较难以统计，可以考虑求出所有极长连续段长度 $\le n - k - 1$ 的排列数量，然后用 $n!$ 减去即可。

考虑枚举 $t$ ，计算所有极长上升段都 $\le t$ 的方案数。考虑一个暴力，先暴力对整个序列分段，令这些段就是极长上升段，然后不难发现限制是 段内 $<$ 和 段间 $>$ 。这个东西非常难以统计，所以考虑容斥掉 $>$ 符号，于是就会让一些上升段合并成同一个大段，而对大段进行分配就非常简单了，因为大段之间被容斥成了无限制，所以这些大段内的分配方案就是 $\frac{n!}{\prod a_i!}$ ，容斥系数就是 $-1$ 的每个大段内小段的个数减 $1$ 次方的积。由于统计大段会比统计小段轻松得多，所以可以转而枚举大段的划分，对于同一个大段划分方案，它的贡献就是 $\frac{n!}{\prod a_i!}$ 乘上每个大段的 每种拆成小段的方案的容斥系数的和 的积。

不妨称每个大段的每种拆成小段的方案的容斥系数的和为这个大段的容斥系数，可以发现这个系数只和大段长度有关。设 $h(a)$ 表示长度为 $a$ 的大段的容斥系数乘上 $-1$ ，因为原本的容斥系数是段间的个数，如果乘上就可以变成段的个数，会更方便统计。考虑转移，可以枚举最后一个小段的长度，由于小段的长度不能超过 $t$ ，所以是

$h(a) = \sum_{i = a - t}^{a - 1} -h(i)$

显然，$h(0) = 1,h(1) = -1$ ，然后发现 $h(2) = h(3) = \cdots = h(t) = 0 , h(t + 1) = 1 , h(t + 2) = -1 \dots$ ，也就是说这东西是循环的，同时只在每 $t+1$ 个位置中有两个位置有值。

看到这题第一想法就是口罩，感觉做过口罩这题的过程就很自然了。我们考虑设 $f(k)$ 表示恰好 $k$ 条边与原树相同的树的个数，$g(k)$ 表示钦定 $k$ 条边，于是：

$\sum_{k \ge 0} f(k)k2^k\\ \sum_{k \ge 0} k2^k \sum_{j \ge k} g(j)(-1)^{j-k} \binom j k\\ \sum_{j \ge 0} jg(j) \sum_{k \le j} 2^k(-1)^{j-k} \binom {j-1} {k-1}\\ \sum_{j \ge 0} 2jg(j) \sum_{k \le j} 2^{k-1}(-1)^{j-k} \binom {j-1} {k-1}\\ \sum_{j \ge 0} 2jg(j)$

然后现在求的就是 $\sum jg(j)$ 这个东西。类似口罩的做法，我们知道钦定 $k$ 条边的时候树的方案数量是 $n^{n-k-2} \prod d_i$ ，后面这团考虑组合意义，相当于是对每个钦定边的连通块选择一个点，前面这团就是 $n$ 的钦定块的数量次幂。再考虑 $jg(j)$ 的这个 $j$ ，仍然考虑组合意义，即从所有钦定边中选择一个边即可。

考虑第一次操作，必然会放在当前 Snuke 的任意一边。

然后考虑第二次操作，必然放在当前 Snuke 的另一边。

然后现在 Snuke 就被圈起来了，仔细考虑一下会发现，它的决策必然是往尽量中间的位置靠。因为在下一次放方块的操作中，你肯定会让 Snuke 的活动范围尽量减少。也就是说，设你放方块的时候 Snuke 到左边长度是 $l$ ，到右边是 $r$ ，那么放完后他的范围肯定是变为 $\min(l,r)$ 。

大概有两种做法。

首先写一下官方题解的做法。

我们设 $i \to P_i$ 存在一条边，同时将 $P_i=-1$ 看做 $P_i = 0$ ，并添加虚点 $0$ ，于是对于任意一个排列，必然可以对应成为一棵树的形态。也就是说现在我们只需要统计这种树的种类数即可。

然后会发现，对于整棵树的一个子树，它必然在序列上对应一个区间，而它的根就是区间的左端点。考虑任意一个位置 $i$ ，它后面的第一个比它大的位置在 $j$ ，考虑 $[i+1,j-1]$ 这一段之间的所有数，显然它们不会连到 $i$ 的前面。再考虑 $j$ 向后的位置，它们不可能连到 $j$ 前面，因此 $i$ 的子树一定是这么一段区间。

神仙构造题。写一下 pb 讲的做法。

考虑极差不超过 $2$ 这个限制。可以把每条边 $u,v$ ，令 $u<v$ ，则变成 $u,v+n$ 的一条边，也就是拆成一个二分图。

考虑在这个图上染色，然后再把 $u,u+n$ 合并起来。如果在这个得到的二分图上可以染色使得每个点极差不超过 $1$ ，那么合并后一定可以让每个点极差不超过 $2$ 。

下面将说明这样的合法的染色方案一定存在。假设一个点 $u$ 的度数是 $ak+b$ ，那么我们可以把一个点拆成 $a+1$ 个点，然后前 $a$ 个点分别得到原二分图上 $u$ 的任意 $k$ 个出边，最后一个得到 $b$ 个出边。然后我们就需要染色后使得每个点的的所有出边颜色不同。

考虑一条边一条边进行染色。假设当前边的两端是 $u,v$ 。现在我们任意找到 $u,v$ 的一对还没有用过的颜色 $c_u,c_v$ 。如果有 $c_u = c_v$ ，显然可以直接给这条边染色。否则，我们把这条边置为 $c_u$ ，然后去寻找一条 $v$ 的出边使得颜色也是 $c_u$ ，假设这条边连向 $w$ ，把这条边置为 $c_v$ ，然后再去找 $w$ 的一条出边使得这条出边是 $c_u$ ，再置为 $c_v$ $\dots$ 就这么一直操作下去。注意，我们寻找的颜色一定是 $c_u,c_v$ 之一。大致过程长成这样：

目前咕咕咕：T6 T8 以及 T5 的 魔改 Min25 。

T1

$T\le 5000,a,b\le 10^9$ 求：

$\sum_{i=a}^b \text{lcm}(i,b) \bmod 10^9 + 7$

前缀和一下即求

$\sum_{i=1}^n \text{lcm}(i,b)$

有一种曾经卷老师教过的非常不错的推法，考虑求和 $\gcd$ 的时候可以直接转乘 $\varphi$ ，

$\begin{aligned} & \sum_{i=1}^n \gcd(i,n)\\ &= \sum_{i=1}^n \sum_{k|\gcd(i,n)} \varphi(k) \end{aligned}$

原因是

$\sum_{a|b} \varphi(a) = b$

那么考虑这个题，我们求

$b\sum_{i=1}^n \frac{i}{\gcd(i,b)}$

我们可以定义一个函数 $f$ ，类似之前的 $\varphi$ 来做

$\sum_{a|b} f(a) = \frac 1 b\\ f \times I = \{\frac 1 x\}\\ f = \{\frac 1 x\} \times \mu$

题目：

Powerful Number 筛也是一种筛，它是 $O(\sqrt n)$ 的。应用时必须满足

• 它是积性函数

• 这个东西在质数处取值的函数可以快速计算前缀和。例如此题，显然有 $f(p) = 1$ 。

首先 Powerful Number 的定义，是所有质因子次数都 $\ge 2$ 的数。这种数的个数是 $O(\sqrt n)$ 级别的。因为显然，每个这样的数都可以被表示成 $a^2b^3$ ，所以寻找这种数的时候可以暴力枚举这里的 $a,b$ ，复杂度是 $\sum_{i=1}^{\sqrt n} (\frac n {i^2})^{\frac 1 3}$ ，这个东西积分一下会发现是 $O(\sqrt n)$ 的。

神仙题。大概是一篇只有做法没有思路的题解。。

显然这个题 $\gcd > 1$ 就是想建补图。然后问题就变成了选出一个点集使得大小正好为 $k$ 且要么每个点都在导出子图里有边，要么所有点都是孤立点。构造一组方案即可。

需要注意的是第二种情况，如果可以找到一个 $\ge k$ 的独立集，那么只需要保留 $k$ 个点即可。

首先要会求所有点的度数。不难发现 $a_i$ 的度数是

$\sum_{1 \le j \le v} occ[j][\gcd(a_i,a_j) = 1]\\ =\sum_{t | a_i} \mu(t) \sum_{t | j} occ[j]$

其中 $occ[k]$ 是 $k$ 这个数在 $A$ 中的出现次数。这个东西可以通过把所有数变成 square free 之后集合枚举，并且预处理 $G[t] = \sum_{j|t} occ[j]$，算出所有数的度数的时间是 $O(2^8 n)$ 。

这场我感觉题很不错的QwQ

C DFS Game

考虑先手到达一个根。然后先手必然会取走这个根上的硬币。然后后手会选择一个儿子向下，然后又变成先手到达一个根的问题。所以感觉上需要考虑 $dp$ 。但是事实上从这个子树回溯回来之后，不一定开始的先手仍然作为先手。所以可以考虑 $dp[u]$ 表示先手到达 $u$ 后可以获得的价值减去后手可以获得的价值的最大值。设最终先手获得硬币数是 $a$ ，后手是 $b$ ，那么 $a+b=n$ ，所以只需要最大化 $a-b$ 即可。

考虑如何转移。不难发现当我们经历完一个子树后是否切换先后手是肯定的，取决于子树的大小，因为每条边都会被经历两次不影响，所以如果大小是奇数则会切换，否则不会。

我们考虑把所有子树按照是否切换分开。那么后手在开始选择子树的时候，一定会先选那些不会切换的，且后手更优的子树，即 $dp[v] < 0$ 的 $v$ ，因为这些东西选了后是一定更优的。这些树选完后一定会选择 $dp$ 值最小的切换的子树。因为选择先手赚的子树是稳亏的。然后选完最小后，曾经的先手就变成了后手，肯定也会选 $dp$ 值最小的切换的子树，只是对答案的贡献变成了 $-dp[v]$ 。于是就变成了一个 $+-+-$ 交替进行的局面。在选择完所有切换的子树后，谁选择剩下的稳亏的子树就确定下来了。

复杂度 $O(n)$ 。

时间好快啊，感觉 SCOI 2020 游记还没写多久就到 2021 年的省选了。

终于，没有了垃圾 SCOI 计算几何。

Day 0

早上看了看字符串板子，该看的板子其实大多都看过了，再复习了一遍 SAM PAM 以及 KMP 之类的，虽然多半也用不上。

下午一直在颓，大概 FC 了个 GOODFORTUNE，希望为明天考试带来好运。

好题。类似 Students Camp 的优化。考虑 $dp[i][j][k]$ 表示当前还剩下 $i$ 个熊两血，$j$ 个一血，其中有 $k$ 个是人。

直接转移复杂度是 $O(1)$ 状态共 $O(n^3)$ 种，复杂度 $O(n^3)$ 。

考虑怎么优化这个 $dp$ 。先把状态转移的式子写出来

$dp[i][j][k] = \frac{i+1}{i+j}dp[i+1][j-1][k]+\frac{j+1-k}{i+j+1}dp[i][j+1][k]+\frac{k+1}{i+j+1}dp[i][j+1][k+1]$

考虑最后答案求的是啥：

$dp[i][j][k]\times k \times (i+j-k) \times (i+j)$

于是我们考虑保留前两维，要求的是

$(i+j)(-\sum_{k} dp[i][j][k] k^2 + (i+j)\sum_{k} dp[i][j][k]k)$

于是我们其实只需要对所有 $dp[i][j][k]$ 乘上 $k,k^2$ 做前缀和即可。

Min_25 筛也是一种求积性函数前缀和的算法。

Min_25 筛的应用前提是可以找到一个完全积性函数在质数处和要求的函数相同。所以我们假装得到了一个完全积性函数 $f'$ 它在质数处的取值和 $f$ 相同。

首先，我们把 $1$ 扣掉，最后把 $1$ 加回来即可。所以后面的范围的下界都是 $2$ 。

我们考虑把所求拆一下，然后在非质数部分枚举一下最小的质因子以及这个质因子的次数：

$\sum_{i \in P} f(i) + \sum_{p^e \le n , p \le \sqrt n} f(p^e) \left( \sum_{i \le \lfloor\frac{n}{p^e}\rfloor,\text{minp} > p} f(i) \right)$

考虑把质数部分和合数部分分开计算。进行一个 $dp$ ：

g(n,k) = \sum_{i \le n , \text{minp} > p_k \or i \in P} f'(i)

即 $2 \sim n$ 中质数或最小质因子大于 $p_k$ 的合数的 $f'$ 的和。

A Strange Addition

水题。

考虑 $dp[i]$ 表示当前考虑到第 $i$ 位，有多少种有序对 $(a,b)$ 在前 $i$ 位满足条件。

转移考虑每次往 $(a,b)$ 后面分别添加一位，然后考虑得到的数，要么得到的数会添加两位，要么只添加一位。所以转移就是

$dp[i] = dp[i-1]S[A_i] + dp[i - 2] S[A_i+10A_{i-1}]$

其中 $S[i]$ 表示有多少种两个一位数加起来是 $i$ 。

A 一次函数

不难发现一个数真正重要的只有这个数中的连续段个数以及这个数最后一位是 $0/1$ 。

我们设 $f(x)$ 表示 $x$ 二进制表示下的连续段的个数。那么答案就是在

$\sum_{i=1}^n f(ai + b)$

的基础上再减去除开最后一个位置的奇数的个数，因为这些数会和下一个数的 $1$ 合并成一段。

A 环游

看起来是毒瘤题，其实不然。

我们设首都是 $a$ ，秘密都市是 $b$ ，新建城市是 $c$ ，我们需要找到的就是一条 $a \to c \to b \to a$ 的路径，且保证 $a \to b$ 有至少三条点不相交路径。

现在假装我们已经拿出了三条 $a \to b$ 的路径。我们考虑先尝试找到一条 $a \to c$ 的路径，然后找出它最后一次经过 $a \to b$ 的三条路径之中的任意一条的某个点 $v$ 。然后我们可以把 $a \to c$ 变成 $a \to v \to c$ ，这样就只会经过一条 $a \to b$ 的路径。再尝试找出一条 $c \to b$ 的路径，找到它第一次经过 $a \to b$ 的某条路径的位置 $u$ ，然后可以把它变成 $c \to u \to b$ ，如果不存在这个位置当然更好。这样我们一共只花费了两条 $a \to b$ 的路径就得到了一条 $a \to c \to b$ 的路径，可以再用一条来返回 $a$ 。

因此可以发现，这个东西有解的充要条件其实就是 $c \to a , c \to b$ 有两条点不相交的路径。

剩下的题有些不可做，可做的也懒得去写了。（咕咕咕

DifferenceSequence

定义对一个序列进行一次操作为

$A_1,A_2,\dots ,A_n\\ \to |A_1-A_2|,|A_2-A_1|,\dots ,|A_n-A_1|$

对于任意一个序列，进行操作后必然会进入一个循环。我们定义循环内的最大字典序串为此串的代表串，求所有长度为 $n$ 的串的代表串去重后字典序第 $k$ 小的串。

我们先打个表观察一下会发现，任意一个序列在进行很多次操作后都会变成一些相同大小的数字与 $0$ 组成的串一直循环。再发现 $n \le 26$ 于是可以枚举所有的二进制串，看看它在进入循环后是否已经有被其他二进制串统计过了，如果没有就把最大的串放入答案。

由于一个串进行操作后得到的串只会被便历一遍，使用位运算来操作，这样做的复杂度是 $O(2^{26})$ 。

A Codechef LUCKYDAY

阴间题。除开卡常和细节还是道很好的题。

$L,R \le 10^{18}$ ，会想到寻找循环节。由于下一个数会和前两个数有关，因此循环结最大不会超过 $p^2$ ，也就是 $10^8$ 级别。但是这个数是可以卡满的，而这题 $500\text{ms}$ 显然不会放过去暴力。

如何找循环节呢，考虑这个转移写成矩乘，设转移矩阵是 $T$ ，于是问题就变成了找最小的 $k$ 使得

$T^{k}A = A$

其中 $A$ 是初始的矩阵也就是

$\begin{bmatrix}a & 0 & 0\\ b & 0 & 0 \\ 1 & 0 & 0\end{bmatrix}$

但是这里不等价于 $T^k = e$ 因为 $A$ 显然不满秩。

我们可以 考虑做一次矩阵 BSGS 来找到循环节。这里复杂度是 $O(P)$ 的，具体来说先把 $T^xA,P | x$ 做 Hash 存进 Hash 表，然后把 $k$ 拆成 $xP - t$ 枚举 $t$ 来查是否存在 $T^t A$ 这个东西。

考虑当前在 $u$ ，如何确定带权重心在哪个子树中。考虑往某个子树移动一个微小距离，那么所有点到这个点距离的变化是

$\sum_{t\notin S_v} (x_t^{1.5} - (x_t - \Delta x)^{1.5} ) - \sum _{t \in S_v} ((x_t + \Delta x)^{1.5} - x_t^{1.5})$

如果这个东西大于 $0$ ，就意味着往这个点移是优的，也就是

$\sum_{t\notin S_v} (x_t^{1.5} - (x_t - \Delta x)^{1.5} ) - \sum _{t \in S_v} ((x_t + \Delta x)^{1.5} - x_t^{1.5})\\ \frac{\sum_{t\notin S_v} (x_t^{1.5} - (x_t - \Delta x)^{1.5} ) - \sum _{t \in S_v} ((x_t + \Delta x)^{1.5} - x_t^{1.5})}{\Delta x} > 0\\$

如果我们设 $f(x) = x^{1.5}$ ，那么就是

$\sum_{t \notin S_v} f'(x_t) - \sum_{t\in S_v} f'(x_t) > 0\\ S - 2\sum_{t \in S_v} f'(x_t) > 0$

我们点分治一下，这样就只需要跳 $\log n$ 次了。