AT 做题记录

· · 个人记录

板刷，好的题（不是水的）记录。并且尽可能给出了多解。（如果题意短，那么给出题意）

AGC001E

求 \sum_{i=1}^n\sum_{j=i}^n\dbinom{a_i+b_i+a_j+b_j}{a_i+a_j} 。

组合意义：\dbinom{x+y}{x} 可以表示从 (0,0) 到 (x,y) ，每次只能右或上走的路径数。问题变为 (0,0) 到 (A_i+A_j,B_i+B_j) 的路径条数。平移得到求 (-A_i,-b_i) 到 (A_j,B_j) 的路径条数。我们把所有的 (-A_i,-B_i) 当成起点，然后一起 \rm dp 即可。

然而

组合意义毁天地，代数推导保平安。

\sum_{i=1}^n\sum_{j=i}^n\dbinom{a_i+b_i+a_j+b_j}{a_i+a_j}=\sum_{i=1}^n\sum_{j=1}^n \sum_k\dbinom{t_i}{a_i-k}\dbinom{t_j}{a_j+k}

第二步用了范德蒙德卷积，其中 t_i=a_i+b_i。

=\sum_k\sum_{i=1}^n\dbinom{t_i}{a_i-k}\sum_{j=1}^n\dbinom{t_i}{a_i+k}=\sum_k F(k)\times F(-k)

其中 F(k)=\sum_{i=1}^n \dbinom{t_i}{a_i+k}。

考虑每一个 \dbinom{t_i}{a_i+k},k\in[-a_i,b_i] 对 F 的贡献，大概就是为区间加一串数 \dbinom{t_i}{0},\dbinom{t_i}{1},…,\dbinom{t_i}{t_i} ，我们直接考虑 OGF，这个 \dbinom{t_i}{a_i+k} 的贡献是 \sum_{k=0}^{t_i}x^{-a_i+k} \dbinom{t_i}{k}=x^{-a_i}(1+x)^{t_i} 。最后的 F 就是 \sum_{i=1}^n x^{-a_i}(1+x)^{t_i}=\sum_{i=1}^m (1+x)^i \times Q_i=(1+x)\bigg( (1+x)\Big((1+x)(…)+Q_2\Big)+Q_1\bigg)+Q_0 ，其中 Q_k=\sum_{a_i+b_j=k}x^{-a_i},最后一步用了秦九韶算法。

这样就可以 \mathcal O(n+m^2) 来搞定这个题了，代码中只要注意一下负数变正即可。

AGC001F

排列 |P_i-P_j|=1 且 k\leq j-i 时，可交换 P_i,P_j， 问能得到的最小的字典序。

这个 K\leq j-i 很麻烦，设一个 Q 为 P 位置与权值交换的新排列，则有 k \leq Q_i-Q_{i-1} 时，可以换相邻的两个 Q_i,Q_{i-1} 。对于 Q 中的两个数 |Q_i-Q_j|<k 则这两个数的大小关系永远不会变，对应到 P 中就是 P_i,P_j \ (|i-j|<k) 的大小关系不会变。

根据这个可以得到 \mathcal{O} (n\times k) 个位置关系，用拓扑排序塞数即可。这里的拓扑排序每次取最值所以用的是堆。

注：限定若干位置的大小关系，构造最小字典序时，有如下常见错误，“直接拓扑排序，当前最小的位置塞最小的数”，而正确的方法是“反边拓扑排序，当前最大的位置塞最大的数”，前者容易找到反例，后者证明略（。

但是 \mathcal{O} (n\times k) 这么多条边肯定不能显性加边。思考删掉一个点为其他点带来的影响，其实就是为 (i-k,i+k) 中 i 的连出点的入度 -1 ，而连入 i 的点可以在删这个点的时候把入度改为 +\infty 即可。这样只要搞一个线段树维护即可。

AGC002D

给出一个无向图，Q 次询问，每次询问给出两个点 (x,y) ，求包含 x,y 的总大小不低于 z 的联通块（可能 x,y不在一个联通块中），使得联通块中的边的序号最大值尽可能小。

看到最大值最小想到二分，直接二分一个上界然后所有上界以下的边都加进来即可。但是是多组询问，所以是整体二分。

整体二分忘得差不多了，再叙述一下全过程：把所有东西都丢到一个序列里， 二分这个序列，同时也二分了答案（注：先处理左半部分，这样递归的时候可以省去删掉左边贡献），序列中产生贡献的东西操作掉，序列中的询问的值查询是否比当前二分值大，考虑丢入左右子区间。

复杂度是 \mathcal O(N\log N) 的，因为每一层都有一个完整的 \mathcal O(N)，总共 \mathcal O (\log N) 层。

具体过程就是二分一个时间节点，把当前队列里的询问查询了扔左右子区间，把时间节点前的图建出来，并查集查询两个点的连通块是否含有超过 z 个点。用可撤销并查集可以少点常数，实际上多开 \mathcal O (\log n) 个并查集就够用。

然而

竟然是 AT 的题，那应该有多解，显然在这个题中，编号比较大的边没有编号小的“有用”，直接考虑 Kruskal 重构树，先加编号小的。但是光是裸的 Kruskal 没有用，还要改进。

为了可以更好得满足二分的性质，我们可以把编号小的节点搞成深度较大，满足一个点不断向上跳经过的边边权越来越大。这样直接二分答案，每个点向上跳，跳到最高处统计能到达的节点数，也就是重构树上节点的 size。这样是 \mathcal{O} (n\log^2n) 的。

AGC002E

有 n 堆糖果，第 i 堆有 a_i 个糖果，每一次可以选择吃掉最多的一堆或每堆吃掉一个。

博弈论的题，吃掉最大的一堆或者全部吃掉都不会改变剩下的堆的排序。

从大到小排序、从左到右排列这些堆糖果，把他变成一个网格图，每次可以从左边或下边消掉一行，全部消掉的时候是必败状态。

转换一下操作，在 (0,0) 点，每次可以往右或往上走一步，边界是必败点。上和右都是必败点的点是必胜点。必胜点的左下必然也是必胜点（易证），剩余都是必败点。从右往左枚举每一个最靠近边界的必胜点，然后计算出他左下碰到底部是哪里，看 (0,0) 这个点是否是必胜点。

AGC002F

给你 n 种颜色的球，每个球有 k 个，把这 n\times k 个球排成一排，把每一种颜色的最左边出现的球涂成白色(初始球不包含白色)，求有多少种不同的颜色序列，答案对 10^9+7 取模。

那么我们设 $dp[i][j]$ 表示在填 $n\times k$ 个空中用完了了 $i$ 个白球和 $j$ 种颜色其他的球，其中 $j\leq i$ 。接下来就是转移的问题了。 如果没有什么限制很容易算重，且转移也不是很好转移，所以加入一些限制使得计算不重复。 对于 $dp[i][j]$ 会算重是因为有两种不同的转移可以得到同一种状态，所以我们钦定每一次转移所有空位的第一个要填上，这样每一次转移得到的状态都只会被计算一次，那么方程也就出来了。（式子也非常好理解） $$dp[i][j]=dp[i-1][j] +(n-j+1)dp[i][j-1]\times \dbinom{nk-i-(j-1)(k-1)-1}{k-2}$$ --- ### AGC003D 给定 $n$ 个数 $s_i$ ，要求从中选出最多的数，满足任意两个数之积都不是完全立方数。$n\le 10^5,a_i \le 10^{10}$。 一个比较简单的想法就是所有数砍掉立方因子，然后对于每个数找出哪个数和他乘起来是立方数。但是由于 $a_i\le 10^{10}$ ，所以无法枚举全部的质因数。 枚举质因数是 $\mathcal{O} (n\sqrt{N})$ 的，然而题目里提到的是完全立方数，那么我们是否可以把这个 $\sqrt{\ \ \ }$ 改成 $\sqrt[3]{\ \ \ }$ 。考虑只用枚举 $\sqrt[3]{N}$ 里的质数，对每个数进行质因数分解，若能分解成功，则可以快速找到对应的数。若不能分解成功，则说明这个数中含有超过 $\sqrt[3]{N}$ 的质因子，设剩下的数为 $s_i$ ，那么若 $s_i$ 是质数且 $s_i\leq \sqrt N$，则对应数中含有 $s_i^2$ ；若 $s_i$ 是一个质数的平方，则对应的数中有 $\sqrt{s_i}$ 可以根据上种情况求出；若上面两种情况都不符合，那么 $s_i$ 含有两个不同的质数为因子，另一个对应的数取值就至少是 $\sqrt[3]{N^4}>N$ 不成立了。 --- ### AGC003E 一串数，初始为 $1\sim n$，现在给 $Q$ 个操作，每次操作把数组长度变为 $q_i$ ，新增的数为上一个操作后的数组的重复。问 $Q$ 次操作后 $1\sim n$ 每个数出现了多少次。 如果前一次的长度大于等于后一次操作，那么前一次操作可以被扔掉，那么我们就可以得到一个单调递增的操作序列。 考虑倒着推，第 $i$ 次操作相当于重复 $\lfloor\frac{A_i}{A_{i-1}}\rfloor$ 次 $i-1$ 次操作后的结果，再加上作为前缀的 $A_i \mod A_{i-1}$ 项。 考虑后面的作为前缀的 $A_i \mod A_{i-1}$ 项是在哪一次操作后最先完整出现，这一步我们可以二分答案，二分出最后比这个余数小的这个位置然后继续取余计算。根据 “一个数对一个比自己小的数取模，那么结果小于这个数的一半” 可以得知，这样做只需二分答案 $\mathcal{O} (\log n)$ 次即可。最后会对应到 $A_1$ 上的一个前缀，然后只要差分一下即可。 总的时间复杂度 $\mathcal{O}(n\log^2n)$。 --- ### AGC003F 由于这个 $k\leq 10^{18}$ 所以可以想到矩阵乘法加速。首先可以处理出一个矩形里有多少 `#` 左右、上下相连；左右、上下相接可以减少的连通块数（这里如果左右可以“粘”住，那么只会减少一个联通块，因为最初的矩阵是四联通的） ；给出矩形中的联通块数量 $c$。 那么 $k$ 阶联通块的数量有当前 $k-1$ 阶的 `#` 的数量 $\times c$，减去左右相连的数量，上下相连的也减去。 一些东西是常量可以预处理，一些东西还要计算，如 `#` 的数量是 $N^k$ ， $N$ 是最初 `#` 的数量；设左右相连的数量是 $H_k$ ，那么 $H_k=H_{1}\times N^{k-1}+H_{k-1}\times h$ ， $h$ 表示两个原始矩阵左右相连可以“粘”合多少块。上下相连也是如此。所有的变量都可以线性递推，所以直接构造矩阵即可。复杂度 $\mathcal{O}(n\times m+\log k)$ 。 --- ### AGC004D 氵 $n$ 个点，每个点向另一个目标点连边（可以是自己），希望修改一些点的目标点，使得从任何一点出发过 $K$ 个边之后恰好都能到 $1$ 号点，求最少的修改次数。 我们可以把 $1$ 自环上，这样是绝对不亏操作的。然后就变成了了一棵把 $1$ 作为根节点的树。我们的连边操作就变成了把这个树切成最小的份数使得每个子树的深度小于 $K$ （包含根节点的那个树的深度可以为 $K$），直接贪心把当前子树深度等于 $K-1$ 的取出即可。 --- ### AGC004E 有一个棋盘，上有若干机器人和一个出口。每次可以命令所有机器人向上下左右中的某个方向移动一格，如果它超出了棋盘的边界就会消失。如果它到了出口的位置就会被你救下(并且从棋盘上消失)。求你能够救下的机器人的最大值。$n,m\leq 100$ 。 可以看成出口在移动，出口移动可以经过一部分区域，同时会带来一部分区域被卡死（如向右移动 $r$ 必然造成最左边的 $r$ 列卡死），那部分被卡死的区域与出口移动经过的区域不交的哪一部分必然会被卡死，否则可能会被救。 我们考虑 $dp[l][r][u][d]$ 表示出口在四个方向上到过的区域，考虑向四个方向转移，例如我们若要将 $r$ 扩展，那么有 $$dp[l][r+1][u][d]=\max\Big\{dp[l][r][u][d] +sum[y_0+r][x_0-u][y_0+r][x_0+d]\Big\}$$ 这个 $sum$ 表示一个矩形里面没死的机器人的个数。也就是扩展出来的机器人个数，减去扩展出来区域中已经死掉的个数。 空间开不下可以用 `short` 来存 $dp$ 的数组。可以减掉多余的转移使得程序常数变很小。 --- ### AGC004F 给一个树或基环树，每个点初始是白色，一条边练的两个点若同色则可以一起变反色。问最少多少次操作可以使得全部点变为黑色或者输出 `-1` 表示不可能。 一次操作会改变两个点的颜色，若有奇数个点，那么无论如何都不可能全变色。如果是一棵树，贪心地每次把白叶子节点和他的父亲反色并且删掉这个叶子即可。这个是可以过树的，但是可以换一种方法考虑： 我们转化模型，颜色这个东西有点抽象，转换成树的奇数层有棋子，偶数层有空位，每次可以把棋子移动到相邻的空位上，问最少次数，这里的图要是二分图才可以这么转换。树的话简单分析一波可以得出 $i$ 号节点到父亲的边上要做的操作数是 $i$ 号节点子树中棋子数量与空位数量的差的绝对值。把空位赋值为 $-1$ ， 棋子赋值为 $1$ ，那么答案就是 $\sum_i |sum_i|$。 如果是基环树，且是偶环，那么先将环为根跑一边上面说的 $\sum_i |sum_i|$。设 $x_i$ 为环上 $i\to i+1$ 边的流量（正负代表方向）。有方程组 $x_i-x_{i+1}=sum_i$ 其中 $1$ 可以看做 $n+1$ 。代表的是基环树上的一条边删去的情况下是 神仙思维题，后面的不会了（**先咕** --- ### AGC005D 问满足对于所有的 $i$ 都有 $|P_i-i|\neq k$ 的排列 $P$ 的个数。$n\le 2000$。 > 如果 $k=0$ （然而这个题 $k\not=0$）那么就是错位排列，先回顾一下：递推式是 $D_n=(n-1)(D_{n-1}+D_{n-2})$ 。考虑第 $n$ 个数占了 $i$ 的位置，若 $i$ 又占了 $n$ 的位置则方案数为 $(n-1)D_{n-2}$ ；否则可以认为剩下的数可作为一个 $n-1$ 个数的错排，其中 $i$ 可以看做不能排第 $n$ 位。对于 $1\le i \le n-1$ 每一个 $i$ 都如此，所以得到了递推式。 正着不好求，那我直接容斥，用 $f(i)$ 来表示钦定至少 $i$ 个地方冲突的方案数。答案就是 $\sum_{i=1}^n (-1)^i \times f(i)$。 我们看到一个点 $x$ 和位置 $x± k$ 有关系我们可以看做边，这样可以把原序列分成若干条链（链中一半是点一半是位置），那么我们可以对每一个链分别考虑（大小相同的链是等价的）：$f[i][j][0/1]$ 表示前 $i$ 个节点选了 $j$ 个边且，第 $i$ 节点和 $i-1$ 节点是否连边的方案数。有： $$f[i][j][0]=f[i-1][j][0]+f[i-1][j][1]$$ $$f[i][j][1]=f[i-1][j-1][0]$$ 朴素 $\mathcal{O}(n^2)$ ：在实现的时候可以把所有链首尾相接一起处理（但是这样新链的起点无法向旧链的终点连边），最终就有 $f(i)=(n-i)!\times f[2n][i]$。（因为 $i$ 是钦定的，所以剩下的随便选）。 **然而** 对于每一个节点数为 $m$ 的链取 $i$ 个互不相邻的边的方案数是 $\dbinom{m-i}{i}$。每个链方案独立的，把所有链的 OGF 卷积起来即可。如果用的是暴力卷积 是 $\mathcal{O}(n\times \frac{n}{k} \times k)$ 的，如果用多项式科技加速可以到 $\mathcal{O}(n\log n)$。 --- ### AGC005E $A$ 和 $B$ 在玩游戏，游戏是在两棵树上进行的，$A$ 在树 $a$上的点 $x$，$B$ 在树$b$ 上的点 $y$ ，两棵树上的点的编号是相同的，只是连边方式不同。$B$ 要追 $A$ ，每次 $B$ 比 $A$ 后移动，每次可以沿着一条相邻的边移动或者不动，问游戏的轮数或输出 `-1` 表示无限轮。 如果先手的树上有一个边连接的两个点在后手树上的距离大于等于 $3$ ，那么先手只要到这个边的端点然后反复横跳就可以完全躲过后手了。如果能到，这就是 `-1` 的情况了。 我们考虑有解的情况，那么先手树上相邻的两点在后手树上距离小于等于 $2$ ，这个时候指定后手的起点为根，那么一旦先手落入后手节点的子树，变无法跳离这个子树（因为先手最多只能跳 $2$）。先手的最佳策略是在不被追到的同时逃往深度最大的点然后等着后手来抓即可。具体实现起来就是如果后手能比先手先到的点先手肯定不能走（易证）。 --- ### AGC005F 给定一棵无根树，定义 $f(i)=\sum_{|S|=i}|V_S| \mod 924844033$。其中 $S$ 是一个点集， $V_S$ 表示包含 $S$ 的最小联通块。 正着做真难，考虑计算每个点的贡献，由于一个点贡献许多 $f(i)$ ，所以直接考虑 OGF。那么 $u$ 的贡献为 ：（第一个式子根据全部减去反面计算的） $$\sum_{i=1}^n \Bigg(\dbinom{n}{i}-\sum_{v\in son_u}\dbinom{sz_v}{i}\Bigg)x^i=(1+x)^n-1-\sum_{v\in son_u}\sum_{i=1}^{sz_v}\dbinom{sz_v}{i}x^i$$ $$=(1+x)^n-\sum_{v\in son_u}\Big((1+x)^{sz_v}-1\Big)$$ 设最后答案是 $\sum_{i=0}^nb_i(1+x)^i$ 然后把他转换成 $\sum_{i=0}^na_ix^i$ 的形式： $$a_i=\sum_{j=i}^n\dbinom{j}{i}b_j=\frac{1}{i!}\sum_{j=i}^n\frac{j!b_j}{(j-i)!}$$ 然后卷积即可。注意 $924844033$ 的原根是 $5$。 --- ### AGC006C 数轴上 $n$ 个点，每个点有起始坐标，一轮包括 $m$ 个跳跃，每次点 $a_j$ 等概率向 $a_{j-1}$ 或 $a_{j+1}$ 对称。经过 $k$ 轮后，求每个点的期望位置。（注意编号是不会变的） 选了一个点 $a_j$ 那他新的期望位置是 $\dfrac{a_{j-1}+a_{j-1}-a_j+a_{j+1}+a_{j+1}-a_{j}}{2}=a_{j-1}+a_{j+1}-a_{j}$ 所以同样有 $E_i=E_{i+1}+E_{i-1}-E_{i}$ 。 做到这里已经可以得到一个 $\mathcal{O}(mk)$ 的算法了呢。考虑如何优化这个东西，我们搞出他的差分 $d_i=E_i-E_{i-1}$ ，那么有一次操作后 $d'_{i}=E_{i+1}+E_{i-1}-E_{i}-E_{i-1}=E_{i+1}-E_{i}=d_{i+1}$ ，$d'_{i+1}=E_{i+1}-E_{i+1}-E_{i-1}+E_{i}=E_i-E_{i-1}=d_i$ 发现一次操作后只会交换 $d_i,d_{i+1}$ 这样 $m$ 次操作可以看成一次置换 ，求 $k$ 次置换可以倍增 $\mathcal{O} (n\log n )$ 也可以 $\mathcal{O}(n)$ 求出循环节。 至于怎么想到的？这种 $k$ 很大的实际问题好多都是模型往置换转换。还有这个 $d_i$ 也是有实际意义的，表示距离。 --- ### AGC006D 题目有点长，题面就不放了。在前面的 B 题中知道一个性质，如果 $i$ 和 $i+1$ 位都是 $x$ ，那么这两个位置就可以直接上传。我们考虑二分最后的答案，把每个数变成 $0/1$ 表示是否大于二分值。如果没有两个相邻位置的值一样那么直接特判，否则可以直接传到最上面（如果有多组，则最靠近中心的那一组是最后的结果），这样可以暴力枚举出来答案，最后用答案来调整下次二分的区间即可。 --- ### AGC006F 你有一个 $N$ 个点的有向图，一开始连了 $M$ 条边，假如存在边 $(x,y)$ 和 $(y,z)$ ，那么你可以连边 $(z,x)$。问最后会存在多少边（自己可以连自己）。 走过两条边后可以再连回去，考虑对一个联通块进行三染色（假设某一个点是红，他连向的所有点就是蓝；蓝连向的所有点都是绿；绿连向的所有点又是红）。 染色失败说明这个联通块最后可以变成完全图，有 $|V|^{|V|}$ 的边。染色成功则红色可以有蓝色的出边，蓝可以有绿的出边，绿可以有红的出边，可以证明，若干次操作过后刚才说的两种颜色间会产生总共 $|\text{红}| \times |\text{蓝}|+|\text{绿}| \times |\text{蓝}|+|\text{红}| \times |\text{绿}|$ 的贡献。 --- ### AGC007C $n$ 个球，$n+1$ 个洞在周围，球洞之间的距离是等差数列，每次随机左右推球入最近的空洞，问期望移动距离的和。（大致这个意思）。 题目给我们的是每个球与其左右的洞之间的距离，那么我们考虑每次推完后剩余可用的球（编号重排）和洞之间的距离的期望。 考虑中间一个求 $i$ 他和右边的洞的距离初始是 $d1+i*x$ ，只有当他右边的第一个球向左边滚才会使得这个距离增加，一番考量过后，发现新的一轮洞和球之间仍然是等差数列，所以我们直接开两个变量纪录当前的第一个数和公差之后转移即可。 --- ### AGC007D 初始的时候位置 $0$ ，出口在 $E$ ，要经过 $n$ 个点两次位置为 $x_i$ ，经过每个点后 $T$ 秒再经过才算第二次，问最小结束的时间。 考虑怎么样才是最优策略，走到了 $i$ 位置，若回头，则要把所有已经经过的都再到一遍，否则明显不是最优解。所以我们设 $f[i]$ 表示前面 $i$ 个位置都去过两遍，在再回到 $a_i$ 的最小时间。 起点是 $f[0]=0$ 终点是 $f[n]+m-a_n$ 。考虑如何转移：枚举从 $j$ 转移，过程就是 $a_j\to a_i\to a_{j+1}\to a_{i}$ 。方程就是： $$f[i]=\min_{j=0}^{i-1}\Big\{f[j]+(a_i-a_j)+(a_i-a_{j+1})+\max\Big(0,T-2(a_i-a_{j+1})+(a_i-a_{j+1})\Big) \Big\}$$ 里面的 $\max$ 很烦，直接分类讨论 $s-2a_i+2a_{j+1}$ 的正负，这个 $s-2a_i$ 单调递减，那么这个临界的 $j$ 就单调递增，直接 `two-pointers` 来求。然后分类讨论的两种情况发现 $\min$ 里面的东西可以只跟 $j$ 有关，所以只要对应开两个单调队列来优化即可，复杂度 $\mathcal{O}(n)$ 。 --- ### AGC007E 比较好的题，之前做过但是再看还是不会。一颗有边权的满二叉树上，有 $m$ 个叶子节点，最小化这 $m+1$ 次路径的权值和的最大值。其中第 $1$ 次起点是根，最后一次终点是根，其他的起点和终点都是叶子，且 $i$ 次的终点是 $i+1$ 的起点，并且每条边都恰好经过两遍。 我们可以二分答案，二分这些路径的最大值，然后考虑设计状态。对于一个节点 $i$ ，设 $(a,b)$ 是 $i\to st\to …\to en$ 是否可行，其中 $dis(i,st)=a,dis(i,en)=b$，那么 $(a,b)=(a,j)_{ls}*(k,b)_{rs}*[j+k\le x]$ 表示枚举 $j,k$ 找到一个可行的那么 $(a,b)$ 就可行。 这么多状态我们肯定开不下也转移不了。所以考虑剪去多余状态，其中对于一个 $i$ 若 $a$ 相同则保留 $b$ 小的，若 $a,b$ 都比某一个大则直接删掉。如何做到去掉无效的状态？以 $a$ 为第一关键字对 $(a,b)$ 排序，然后保证 $b$ 递减即可。合并的时候要求 $j+k\le x$ 所以只要用双指针即可。 关于复杂度，设 $g_u$ 表示 $u$ 节点的状态数，那么 $g_u=2\times \min(lev_{ls},lev_{rs})$ 是最多的状态，这里的 $2$ 只影响常数，只有小的会贡献，相当于启发式合并，所以 $\sum_u g_u$ 是 $\mathcal{O}(n\log n)$ 的，那么算法总的复杂度就是 $\mathcal{O}(n\log n\log N)$。 --- ### AGC007F 两个字符串 $S_{0}$ 和 $T$ ，请求出使得 $S_{i} $ 有可能与 $T$ 相同的最小的整数 $i$ 。如果这样的 $i$ 不存在，请输出 `-1`。 其中 $S_i[j]=S_{i-1}[j]$ 或 $S_i[j]=S_i[j-1]

（我愿称之为模拟神题）

每一次操作相当于是把若干段不相交的区间全部覆盖成区间第一个位置上的值。如果这个区间的前缀之后被覆盖，则需要第二次操作。观察样例或者略加思索得出，对于每一个 T[i] 找到 S_{0}[j]=T[i] (j\le i ) 中最大的 j，这个区间是要被操作的，如果这个区间被别的区间覆盖，那么就无解，如果找不到这样的 j，也无解，如果两个区间相交，则后面的区间要先做。

我们可以从后往前考虑，每次直接覆盖到能到达的最右（或者是目标位置），然后把这些覆盖到的位置标记成不能到达。画个图可以知道，只要维护上一个考虑的元素在那几个位置向后覆盖了多少即可。（偷一张 ouuan 巨佬画的图更好理解）

AGC008E

给定正整数 n 和一个长度为 n 的序列 a ，问有多少长度为 n 的排列满足对于任意的 i 有 p_i=a_i 或 p_{p_i}=a_i。

把一个位置抽象成点， p_i 表示 i\to p_i 的边，那么问题就成为对于每一个点 i 要么 i\to a_i 有边，要么 p_i 即 i 出边的点与 a_i 有边，也就是构造一个 n 个点 n 个边的有向基环树森林使得每个点 i 都可以在两步之内到 a_i。 因为 p 是排列，所以这个图是若干个环（没有入度为 2 的点）。

取出一个环，考虑所有的情况，擦掉原来的边，加上 i\to a_i 的边。

  1. 所有 a_i 都是 i 前面的点，新图就和原来一样。

  2. 所有 a_i 都是 i 前面的点的前面的点，且这个环是奇环，这样新图就是另一个环。

  3. 所有 a_i 都是 i 前面的点的前面的点，且这个环是偶环，这样新图就分裂为两个大小为原来一半的环。

  4. 剩余其他所有情况都会把新图变成一个基环树。

求 p 的过程反着考虑，先找到所有环，纪录每种大小的有多少个，答案是 \sum_{j\le \frac{cnt_i}{2}}\dbinom{cnt_i}{2j} \times \dbinom{2j}{j}\frac{j!}{2^j}\times i^j 或者 \rm dp 来考虑。再计算基环树的情况数，我们考虑把基环树的树链往环里面塞，画个图就知道，这个方案数与两条链之间可以被塞的空有关，只能塞 0/1/2 种情况。最后把所有数都乘起来就是答案了。

AGC009D

简化版：最优树的点分治，使得点分最大层数最小。

可以把每个点的层数当做一个这个点的一个标号值，那么要使条件成立，必然有每两个标号相同的点的路径上存在一个标号更大的点。

我们可以考虑进行 \rm dp ，设 b[u][i] 表示 u 的子树内的所有 i 标号是否还未完全匹配了，由于点分治的性质，我们发现 i\leq \log n 所以 i 的这一位可以压成一个数。 考虑转移 ，我们把 u 节点的所有叶子 v 的 b[v] 或起来得到 t，若 t_k=1 则表明 u 不能放 k。还有一个约束， 若存在 b[v_1][k]=b[v_2][k]=1 那么 u 一定放的是大于 k 的，将所有的 b[v_1] \And b[v_2] 或起来得到 s，那么 u 上放的数是 s 的前导零，在 t 对应位置是 0。

把状态压成一个数后，用 __builti 函数即可 \mathcal{O}(1) 计算上述过程。总的时间复杂度是 \mathcal{O}(n) 。

AGC009E

黑板上有 n 个 0 和 m 个 1，我们每次选择 k 个数字将其擦除，然后把它们的平均数写上去，这样一直操作直到只剩下一个数字，问剩下的这个数字有多少种不同的情况。n,m,k\leq 2000，保证 k|(n+m-1)。神仙题。

考虑模型转换，把这个东西转换成一个 k 叉树，叶子节点是 n 个 0 和 m 个 1 ，非叶子节点是他儿子节点的和的 \frac{1}{k} ，根节点的值就是答案。

设 n 个 0 的深度是 x_i，m 个 1 的深度是 y_i ，那么有 \sum_{i=1}^m \frac{1}{k}^{y_i} 就是根节点的值。但是这个 y_i 的取值有限制，满足这个限制

\sum_{i=1}^{n}(\frac{1}{k})^{x_i}+\sum_{i=1}^{m}(\frac{1}{k})^{y_i}=1

我们再转换问题，问的是有多少个 z 可以表示为 \sum_{i=1}^m \frac{1}{k}^{y_i} 且 1-z 可以表示为 \sum_{i=1}^n \frac{1}{k}^{x_i} 的形式。把 z 写成 k 进制小数，有 z=0.c_1c_2c_3c_4… 其中 \sum_i c_i \equiv m \ (\mod k-1) 取模是因为要进位 ；那么 1-z 的位数和就应该是 (len-1)(k-1)+k-\sum_ic_i \equiv n \ (\mod k-1) 。

这下就可以 \rm dp 了，dp[i][j][1/0] 表示到了第 i 位，每一位的和是 j ，最后一位是否是 0 的方案数 （注意最后一位不能是零）。

AGC010C

有一棵树，第 i 个节点上有 a_i 个石头，每次选择两个叶子节点，将路径上经过的所有节点上都取走一个石头，如果路径上有一个点上没石头这个操作就不能进行，问能不能取完所有石头。

设 f_u 表示从 u 节点向上的路径条数， s_u=\sum_{v\in son_u}f_v。有 a_u=\frac{s_u-f_u}{2}+f_u \to f_u=2a_u-s_u。

可以证明 当这两个条件成立的时候，总能构造出合理的方案：\color{red}{1.} \max_{v\in son_u} f_v\le a_u，\color{red}{2.} 0 \le f_u \le a_u \color{red}{3.} f_{root}=0。

AGC010D

有 n 个数 A_i，\gcd_{i=1}^nA_i=1 。两个人轮流操作，每一次可以取一个大于 1 的数使他 -1，并让所有数除以 \gcd_{i=1}^nA_i，无法操作的人输，问是否先手必胜。

$\color{red}引理2$：如果有奇数个偶数，则先手必胜。 证明：先手可以保证每次两个人都只能取一个：每次的局面都存在一个偶数减一（考虑反面易知），变成至少两个奇数，并且这之后后手只能取一个，那么局面又回到了奇数个偶数。（特殊情况是序列长度为 $2$）。 同样的，这时后手遇到的局面是 至少两个奇数和偶数个偶数，那么就是必败的。 其他情况下，也就是有偶数个偶数和一个奇数，然后让这个奇数 $-1$ 整体除以 $\gcd_{i=1}^nA_i$ （注意不是 $2$ ） ，如果不这么做就会变成引理 2。这样的操作总数是 $\mathcal O (\log N)$ 的. --- ### AGC010E 有一个 $n$ 个数组成的序列 $a_i$，高桥君会把整个序列任意排列，然后青木君可以选择两个相邻的互质的数交换位置。高桥君希望最终序列的字典序尽量小，而青木君希望字典序尽量大。求最终序列。 若 $a_i,a_j$ 不互质，则 $a_i,a_j$ 的相对位置不会改变，根据操作性质可以得出。那么转换一下模型，先手就是给一个无向图的每个边确定方向，其中不互质的两个点连变，表示这两个点最原始的位置关系。而后手则是对这个 $\rm DAG$ 做一个拓扑排序，找到最大的字典序，实际上是反着加边然后用优先队列来搞的。 为了使最后的字典序尽量小，那么直接贪心地把最小的点往前面放，连向更大的点，表示先要取出小的才能取出大的。这样的结果是搞出一个生成树，对于非树边，只要按照深度来不形成环即可。 --- ### AGC010F 一颗 $n$ 个点的带权树，先手会在一个节点上放一个棋子，从先手开始，他们进行以下操作，将棋子节点的权值 $-1$，选择一个相邻的权值不为零的节点移动棋子。如果有一个人移动之前该节点权值就变成 $0$ 了，那么他就输了。 考虑最初始的节点 $u$ ，对于他的相邻节点 $v$ 若有 $a_v>=a_u$ 则 $u$ 无法去到 $v$ （后手会让棋子移回来，这样就输了）。那么 $u$ 只能去到 $v$ 其中 $a_v<a_u$ ，那么在去到 $v$ 的过程中能不能去到其他的地方“蹭”一下呢？ 答案是否定的，因为 $a_v<a_u$ 所以到了 $v$ 之后，后手是不会想要回到 $u$ 的，因为上述原因，所以可以看做 $a_u$ 的大小不会影响后面的操作。如果去蹭了，那么 $a_u$ 会无端减小，对于先手来说不利。这个时候就可以得到结论了：每次都只会去权值较小的节点，其他节点不会去，且不会原路返回。这样就转换成只要套一个必胜/必败点的板子了。 --- ### AGC011C 给定一张有 $n$ 个点，$m$ 条边的原图，现构成一张新图，其中每个点都是一个二元组 $(a, b)$ 。$2$ 个二元组 $(a, b),(c, d)$ 有边当且仅当 $a$ 和 $c$ 有边且 $b$ 和 $d$ 有边。现求新图联通块个数。 新图中连边的过程我们可以看做 $a$ 走到了 $c$ ，$b$ 走到了 $d$ 。考虑点 $(x,y)$ 与 $(x',y')$ 在同一个联通块里面要满足什么条件。那就是从 $x,y$ 出发可以同时到达 $(x',y')$ 也就是 原图中存在一条 $x\to x'$ 和一条 $y\to y'$ 且他们的长度相同。因为是无向图，所以可以两个点反复跳，最后只要存在奇偶性相同的路径即可。 所以下面分三种情况考虑 1. 对于原图中的一个独立点 $x$ 有 $(x,i),(i,x)$ 都是独立的点，设总共有 $s_1$ 个这样的点，可以对答案贡献 $s_1n+(n-s_1)s_1$。 2. 对于原图中一个不包含奇环的连通块，他可以和原图中不包含奇环的连通块形成两个新连通块，设这样的连通块有 $s_2$ 个，那么对答案的贡献为 $2s_2^2$。 3. 对于原图中一个包含奇环的连通块，显然这个连通块中处处路径可奇可偶，所以可以和另一个连通块形成一个新联通块，设这样的连通块有 $s_3$ 个，贡献为 $s_3^2+s_3s_2$。 然后发现 $2$ 可以对 $3$ 造成 $s_2s_3$ 的贡献，输出答案这个题就完成了。 --- ### AGC011D 有 $N$ 个机器排成一排，有两种状态，`A`：会把球反弹（即让球反方向滚动）`B`：让球自由通过（即让球沿原方向滚动）；然后每有一个球撞上机器，这个机器就会改变状态。现在给你$N$个机器的初始状态，然后你将一个球滚进去 $K$ 次，问 $K$ 次后机器状态。 挺有意思的一个题，可惜可以找规律，打表或者怎么样可以得到如果第一个是 `B` 那么撞过一遍之后会把所有数取反然后左移一位，最后少的那一个用 `A` 来填。（这个好证明，这里不再赘述） 然后我们会发现每次取反过后最后的几个会是 `…ABABABA…` 这样的，这样只要最多 $2n$ 次撞击即可把这个序列变成 `A` , `B` 相间的数列然后看看剩余 $K$ 的奇偶性即可。前 $2n$ 次撞击直接模拟，最后的复杂度是 $\mathcal{O} (n)$ 的。 --- ### AGC011E 现在给你一个数 $n$ ，问最少可以被表示成几个递增的数之和。递增的数是任意左边数位都小于等于右边的数位。其中 $n\leq 10^{500000}$ 。 上升数可以写成 $\sum _i \frac{10^{k_i}-1}{9}$ 表示这个数可以由若干个全 $1$ 的数相加得来。我们二分一下总共用了 $m$ 个上升数，那么有 $n=\sum_{i=1}^{9m}\dfrac{10^{p_i}-1}{9}$ ，上过小学的你一定可以推出这个 $9n+9m=\sum_{i=1}^{9m}10^{p_i}$ 。考虑进位的话就是 $9n+9m$ 这个数的所有位数之和 $s$，有 $s\equiv 9m \ (\mod 9) \to s\equiv 0(\mod 9)$ 且 $s\ge 9m$ ，又发现 $9n+9m$ 这个数是 $9$ 的倍数，而 $9$ 的倍数的数位和也是 $9$ 的倍数，这样就只要考虑 $s\ge 9m$ 即可。在程序中我们枚举 $m$ ，然后维护一个大整数加法就好了。可以证明复杂度是 $\mathcal{O}(\log n)$ 的，这里均摊的高精度是 $\mathcal{O}(1)$ 的。 ---