About Me

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

目前咕咕咕：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$ 次了。

A Power

看到这题数据随机就可以想到可不可以乱搞。我们考虑从 $P-1$ 开始向下枚举，每次用 BSGS 解出这个数第一次出现的位置，如果这个数小于之前的最小位置，我们就用它来代替最小位置继续做。然后考虑设置一个阈值 $B$ ，如果当前的数已经小于了 $B$ 就停止这个做法直接枚举前 $B$ 个数。

然后写出来试了试发现只能过 $10^7$ 。冷静分析一波复杂度，会发现如果 $B$ 控制合理大概是 $O(P^{\frac 3 4})$ 的东西。具体来说，随机情况下如果我们找到了一个比当前最优位置小的位置，就期望可以让最小值减半。而出现这种数的时候大概是一个线段树的结构，我们可以认为出现这种数的概率是 $\frac1 {2^k}$ 这种东西。总的来说，期望可以用 $O(\frac P B T)$ ，其中 $T$ 是 BSGS 查询一次的复杂度，来让规模减小到 $B$ ，最后暴力复杂度是 $O(B)$ 。然后发现如果优秀地调整 BSGS 块的大小复杂度是 $O(P^{\frac 2 3})$ ，但是还是常数太大。然后考虑减枝，也就是在 BSGS 的时候如果当前都已经大于最小值就不管了，这些优化都加上后，会发现可以过 60 分，本机跑极限数据也只需要 1.6s~1.9s 可惜 OJ 太慢过不去。

任意模数下的积和式并没有多项式解法。考虑积和式的组合意义，$i,A_i$ 都是互不相同的，可以看作是二分图的一个完美匹配。因此任意矩阵的积和式就是 $A_{x,y}$ 看作左侧 $x$ 右侧 $y$ 之间的边权后所有完美匹配边权的积的和。

如果我们给所有 $A_{x,y} \neq 1$ 拆成 $1,A_{x,y} - 1$ 这两个东西，然后所有边上都有了一个长度为 $1$ 的边。于是现在就可以不考虑所有长度为 $1$ 的边了。我们求出除开边权为 $1$ 的边后的任意一个二分图匹配，那么这个匹配的贡献直接乘上未匹配点的个数的阶乘即可。因为剩下的点都可以任意匹配，而且一定可以通过 $1$ 边匹配上。

但是这样点的数量还是 $O(2k)$ 的。我们可以考虑对每个连通块分别计算，然后乘法原理乘起来即可。这样每个连通块内的点数就一定不超过 $k$ 了。一种很容易想到的做法是对每个连通块做状压 $dp$ ，考虑把点数较小的一边压成状态，然后枚举点数较多的一边来做 $dp$ ，这样做一个点数为 $n$ 边数为 $m$ 的连通块的复杂度是 $O((\frac n 2+m)2^{\frac n 2}) $ 。这样是过不去的，如果卡满就是 $50 \times 2^{25}$ 。

考虑另外一种做法，求出这个二分图的一棵生成树，然后对于所有环边枚举环边的选取情况，然后在树上做一次背包来解决。这样做的复杂度是 $O(2^{m-n} n^2)$ 。

以前做的，没发博客。

如果两个串的 endpos 等价类相同，显然把任意一个放进 $s_i$ 里面是一样的效果。

于是我们可以建出 SAM 的 fail 树，考虑做 $dp[u]$ 表示当前在树上的 $u$ 节点，同时我们最后一次选择的是这个点上的最长串，最多可以选出的序列长度。

显然，我们选择一个深度更大的位置比选择一个深度更小的位置作为序列的上一个位置好。因为深度更小的位置一定在深度更大的位置的所有 endpos 中出现过。所以我们可以考虑找到最深的一个位置，满足这个位置在当前串中出现过至少两次。

我们可以进行可持久化线段树合并，然后倍增来跳这个位置。如果一个位置 $v$ 满足，即意味着在 $rt[v]$ 的线段树里面在 $[r-len[u]+len[v],r-1]$ 之间有过值，也就是有过 endpos 。

直接进行线段树区间查询即可。

Ｂ口罩

太经典的题了，以前这场之后都见过两次了。

考虑钦定 $k$ 条边，然后把这 $k$ 条边删掉，再加入回去，求有多少种树。最后再二项式反演回去即可。

一个结论：有一个 $n$ 个点的森林，其中有 $k$ 个连通块，设每个连通块大小是 $d_i$ ，连边可以形成的树的个数是

$n^{k-2} \prod d_i$

考虑 $\text{prufer}$ 序，构造一个长度为 $k-2$ 的值为 $1 \sim n$ 的 $\text{prufer}$ 序。然后还原方法是把连通块看成点，把 $1 \dots k$ 写下来，每次找到最小的没有一个点在 $\text{prufer}$ 出现的连通块拿出来，和首项连边。连边的时候会找到当前连通块的一个点去连。序列长度为 $2$ 则直接分别选一个点连。而每个 $1 \dots k$ 的连通块都正好需要选一次点，所以乘上每个连通块的大小。

然后可以发现，$\prod d_i$ 本质上就是把树分成若干个连通块，每个连通块选正好一个点的方案数。所以我们可以 $dp[u][k][0/1]$ 表示当前在 $u$ 选了 $k$ 个连通块出来了，$u$ 所在连通块是否选点。树形 $dp$ 即可。

复杂度根据某经典证明是 $O(n^2)$ 的。

好题。也是一个会一半的题目，最后一半是一个没怎么见过的套路。

考虑字典序比较，常见的方法是枚举 $\text{LCP}$ 长度，然后固定下一位小于，然后剩下的随便放。

在这个题中，我们一样可以枚举 $\text{LCP}$ 的长度，比如长度为 $k$ ，也就意味着第 $p_1 \dots p_k$ 小在 $A,B$ 中是相等的，而 $A$ 的第 $p_{k+1}$ 小比 $B$ 的小。

我们考虑对两个集合分别排序后处理。对于每个 $k$ ，我们考虑 $p_{k+1}$ 处 $A$ 的取值对答案的影响，设这个位置到左边第一个已经确定的位置中间有 $l$ 个空位，这个位置到右边第一个有 $r$ 个空位，这个位置到两边的值域分别由 $L,R$ 个数，那么贡献是是

$\sum_{c \ge B_{k+1}} \binom{c-L}{l} \binom{R-c}{r}$

而这个位置一旦确定，也就是枚举到了 $k+1$ ，那么相当于是删除前后位置间这一段的贡献，加入新的两段的贡献。明显这个贡献是个组合数。

CF Edu 30

E Awards For Contestants

考虑枚举前两个奖分别有多少人获得，然后会发现合法第三种奖的数量形成了一段区间，我们可以预处理 RMQ 来快速得到第三种奖的最大 $c_3 - d_{-1}$ 这个东西。

然后复杂度就是 $O(n\log n + n^2)$ 了。