202410 测试笔记兼停课记录

前言：定义 $2024/10/26$ 为 Day $1$。

吸收暑假教训，励志补完每一套测试题！2024/10/10：感觉是补不完的了。

$2024/10/9\sim 2024/10/25$ 为停课集训期。

---

$2024/9/28$

今天本来要上文化课（我们 $9/30$ 放到 $10/7$，本日不放假），我们直接旷课来上课……

早上 Lgx_Q 讲动态规划，下午测试：

T1 AT_abc354_d [ABC354D] AtCoder Wallpaper

解析：不想写，弱智找规律，不知道为啥还能有绿。

$2024/10/13$ UPD：还是写点注意事项吧。将 $x,y$ 坐标全部加上 ${10}^9$ 变为正数方便处理，由于 $2$ 行一个规律，$4$ 列一个规律，$4\mid {10}^9$，所以答案不变。

由于列的规律更多一点，所以先拿两个变量算出 $[x_1,x_2]$（题目要查询的矩形的左右边界）在 $2$ 种行分别是多少，再算出有多少个第一种行，多少个第二种行就好了。

T2

简要题意：在 $1\sim n$ 中挑出 $l$ 个数组成序列，要求相邻的数奇偶性不同，且序列严格单调递增，求不同的序列的方案数。（$n,l\le {10}^5$）。

解析：设组成的序列是 $a_1,a_2,\dots ,a_l$，由于相邻两个数奇偶性不同，相邻的数的下标的奇偶性也不同，所以 $b_i\leftarrow a_i-i$，所有 $b_i$ 的奇偶性相同，其中 $b_1\ge 0$，$b_l\le n-l$。枚举 $b_1$，那么 $b_2$ 有可能是 $b_1$（由于 $2>1$，所以只要 $b_2\ge b_1$，$a_2$ 绝对大于 $a_1$，以此类推），$b_1+2$，$b_1+4$ 等等，插板法即可计算方案数。

这是一个 trick 吗？不知道是怎么想出来减去下标的。

T3 P7967 [COCI2021-2022#2] Magneti

解析：设 $f_{i,j,k}$ 表示前 $i$ 个数组成 $j$ 段答案花费了 $k$ 的距离。

• $i$ 自己开一段答案：$f_{i,j,k}\leftarrow f_{i-1,j-1,k}$。

• $i$ 接到之前的某一段答案，还有左右加入之分，所以要乘上 $2$：$f_{i,j,k}\leftarrow f_{i-1,j,k-r_i}\times 2j$。

• $i$ 合并左右两段答案，放在中间要花费左右 $2$ 倍的距离，此外，不知道合并哪两个序列，直接乘上 $\frac{n(n-1)}{2}$，但是同样有左右之分，再乘上 $2$ 分母就没了：$f_{i,j,k}\leftarrow f_{i-1,j+1,k-2r_i}\times n(n-1)$。

最后统计答案：对于每个 $f_{n,1,i}$（$n$ 个磁铁花费 $i$ 的距离组成一段答案），剩下的空位还可以随便放，乘上组合数：

$$ans=\sum _{i=0}^l{f}_{n,1,i}\times C_{l-i+n-1}^n$$

考场想到一个很不正的做法，多组数据样例错一组，不会改，没有想，喜提 $6$ 分，好像也没人是那样做的。

这个正解是很典的排列 DP，但我测试时还没掌握排列 DP qaq。

$2024/10/5$

依旧早上 Lgx_Q 讲课下午测试。

T1 P6471 [COCI2008-2009#6] DOSTAVA

解析：横着走直接前缀和处理，每一行的两端构成一张点数为 $2r$ 的图，以每个点为起点跑一次单源最短路，再写多几个判断从这个点到另一个点的那一行最短怎么走（式子贼抽象，且很容易想到，这里就不摆了）。额外要注意同一行不用跑最短路，直接用前缀和处理即可。

忘记处理同一行的情况爆挂 $30$，再加上 GJOJ 测评机飞慢，洛谷上 $1.2\text{ s}$，GJOJ $3\text{ s}$ 还 TLE，再挂 $30$，无敌了。

T2 AT_abc176_f [ABC176F] Brave CHAIN

解析：设 $f_{a,b}$ 表示现在手上拿着 $(a,b)$ 两张牌的最大价值。

对于取 $max$ 的题，初始时 $f$ 要赋成 $-\mathrm{\infty }$ 而不是 $-1$，不然挂大分。

$f_{a,b}\leftarrow 0$。当然码代码时为了方便操作正反两种顺序的状态都要修改。

设下一波进来的三张牌分别是 $x,y,z$。

1. 有贡献的情况

(1). $x=y=z$

直接扔掉新进来的三张，它们不参与后面的转移，所以用一个 $an{s}^{\prime }$ 专门计数这种情况。

(2). 有两张牌相同

根据异或的性质，$dif\leftarrow x\oplus y\oplus z$ 即可得到不同的数，$same\leftarrow \frac{(x+y+z-dif)}{2}$ 即可得到相同的两个数。如果现在手上拿着 $j$ 和 $same$，那么可以留下 $j$ 和 $dif$：$f_{j,dif}\leftarrow f_{j,same}+1$。

此外，如果手上拿着两张 $dif$，也可以留下两张 $same$，$f_{same,same}\leftarrow f_{dif,dif}+1$

(3). 三张牌都不相同

如果手上拿着两张 $x$，可以留下 $y,z$：$f_{y,z}\leftarrow f_{x,x}+1$，剩下两种情况同理。

2. 没有贡献的情况

(1). 留两张新进来的牌

直接 $f_{x,y}\leftarrow ans$，$ans$ 表示目前可能的最大贡献，剩下两种情况同理。

(2). 留一张新进来的牌

$f_{x,j}\leftarrow max\{f_{j,?}\}$，后面这一部分可以用一个数组 $g$ 维护，另外两种留 $y,z$ 的情况同理。

转移太多，不好写，可以用一个 vector 之类的存下当前这一步所有要转移的 DP 的信息，在这一步的最后用循环拿出来提取信息转移。

其实思路和做过的 CF82D Two out of Three 思路很像，但这个转移太复杂，考场没想清楚，直接觉得不可转移。

$2024/10/6$

依旧早上 Lgx_Q 讲课下午测试。

T1 GYM101741J Subsequence Sum Queries

解析：分治 + DP 好题。

把所有询问离线下来，用 solve(l,r) 来解决位于 $[l,r]$ 且跨过区间的 $mid$ 的问题。这些问题有哪些可以用 vector 存，准备递归下一层时再全部提出来分类丢进左右两边区间的 vector。

先从 $mid$ 往左 DP 找到从 $mid$ 到 $i$ 这个位置，和模 $m$ 等于 $j$ 的子序列个数，$O(m\times len)$ 可求，记得还要继承 $i+1$ 的状态。从 $mid+1$ 往右同理。

然后处理跨过 $mid$ 的问题，假设问题询问的是区间 $[q_l,q_r]$，显然答案等于：

$$f_{q_l,0}\times f_{q_r,0}+\sum _{i=1}^{m-1}(f_{q_l,i}\times f_{q_r,m-i})$$

加上分治的时间复杂度，总时间复杂度为 $O(nm\log n)$。

T2 P7242 [COCI2019-2020#4] Klasika

解析：两点间的路径异或权值，就是根到两点的异或权值再异或起来，沿用 P4551 最长异或路径 的思路，建一棵 01Trie，询问根到其中一点的时候，往另一点反方向跑。

用一个 vector 存起来每个节点为询问终点的问题，当处理完这个节点的所有子树时用启发式合并的方法（轻儿子合并到重儿子上）合并子树，然后处理这些问题。

对于询问和增加先后的问题，打个时间戳写个可持久化的东西，然后进入节点的时候判断时间戳是否合法即可。

$2024/10/7$

早上测试，下午是一个不认识的学长讲题，然后难得有时间调题，把 $28$ 号和 $5$ 号的题给补了。

T1

简要题意：大模拟有概括的必要吗。

死去的麻州扑克开始攻击我。

解析：假定已经选好了两个雀头，可以发现剩下的牌里面，有三个一对的一定可以先取出来，所以从小到大取即可，用一个计数数组 $f_{i,j}$ 表示 $i$ 号牌 $j$ 花色还剩多少张，模拟就行了，这一层时间复杂度 $O(n\log n)$。排序完之后相同的牌面一定挨在一起，所以枚举两个雀头再套一个 $O(n)$。

情况二就直接再暴力枚举加哪张牌就行了，套个常数，再加上 $T$ 组数据，总复杂度 $O(30T{n}^2\log n)$，不要太宽裕。

T2 P8191 [USACO22FEB] Moo Network G

解析：观察到 $y_i$ 很小，可以从这里下手，贪心可以得到每个点只需要向每一层 $y_i$ 左右离自己最近的点连边跑最小生成树即可。证明：

• 设存在三个点 $A(a,m)$，$B(b,m)$，$C(c,n)$，$m\ne n$ 且 $a<b\le c$，即 $A$ 点不是 $C$ 点在 $m$ 这一层向左最近的点。

• 易得 $\mathrm{△}ABC$ 是直角三角形或钝角三角形，其中 $AC$ 是最长边。直角三角形两短边平方和等于第三边平方，钝角三角形则是小于。按照 Kruskal 的贪心逻辑，一定会先连上 $AB$ 和 $BC$，$AC$ 没用，证毕。

什么**样例，点的编号和横坐标写混了垃圾样例没测出来，爆挂 ${94}^{\prime }$。

T3

简要题意：一个有向图有 $n\le 3\times {10}^5$ 个点，$m\le 6\times {10}^5$ 条边，求点集的连续非空子集，满足子集中每一个点的直接后继都属于子集的子集个数。

解析：考虑分治，每层分治处理跨过 $mid$ 的子集。

用 $p_i$ 统计点 $i$ 出度里编号最小的点，$q_i$ 统计出度里编号最大的点，只有这两个点会影响答案。如果子集 $[l,r]$ 符合题意，那么有 $\mathrm{\forall }i\in [l,mid]$，$p_i\ge l$（1），$q_i\le r$（2）；$\mathrm{\forall }i\in [mid+1,r]$，$p_i\ge l$（3），$q_i\le r$（4）。

对于（1）（4），只需要从 $mid$ 往左右做两次线性的递推就可以得到个数，用一个数组存起来。对于（2），往左递推的时候，维护左半部分 $q$ 的最大值 $mq$，右半部分下标小于 $mq$ 的都是不合法的答案；对于（3），在右半部分找到第一个 $r^{\prime }$，使 $p_{r^{\prime }}<l$，那么 $r^{\prime }$ 及后面的都是不合法的答案，由于向左递推时 $l$ 单调递减，所以 $r^{\prime }$ 可以线性递增。

那么做法就出来了：先把右区间的（4）处理出来并存进前缀 $f$ 里，然后往左递推；枚举子集的左端点 $l$，同时维护（1）（2）（3），如果满足条件（1），将条件（3）和条件（2）在前缀和里取一下就行了。

T4 P8189 [USACO22FEB] Redistributing Gifts G

解析：考虑建图，节点 $i$ 向每个不是它更不喜欢的礼物连边，发现合法的方案都是将这些点放在了若干个环上。

设 $g_s$ 表示点集状态为 $s$ 的情况时，组成环的方案数。设 $h_{s,u,v}$ 表示点集状态为 $s$ 的情况时，从 $u$ 走到 $v$ 的方案数。初始时，$h_{2^i,i,i}\leftarrow 1$。

当 $j$ 不是 $s$ 的子集时，走过去：

$$h_{s\vee 2^j,u,j}\leftarrow \sum _{i\subseteq s}{h}_{s,u,i}$$

当 $j$ 是起点 $u$ 时，成环了，存起来：

$$g_s\leftarrow \sum _{j=u}{h}_{s,u,i}$$

铁定超时，发现瓶颈在枚举每种点集状态的起点，但这是完全没必要的，可以直接让 $s$ 这一子集中最小的点 ${\log }_2(\text{lowbit}(s))$ 来当起点，优化掉一维。

接着考虑解决问题，设 $f_s$ 表示有一组奶牛的状态是 $s$ 时的方案数，显然最后答案是 $f_s\times f_{s\oplus U}$（$U$ 表示全集），这个转移也很好理解。

$$f_s\leftarrow \sum _{t\subseteq s}(g_t\times f_{s\oplus t})$$

$O(3^n)$ 枚举子集的模板：

for (int s = 1; s < 1 << n; s++)
    for (int t = s; t; t = s & (t - 1))

$2024/10/8$

什么？我能停课？什么？我能停课？什么？我能停课？

我期待这一天已经一天了，得亏我 $7$ 号晚上刚把东西全部搬回 ss $8$ 号晚上又要全部搬回家。

$2024/10/9$

早上 $10$ 点来学校，$8$ 人舍 $\leftarrow 5\mathrm{ss}+2\mathrm{nf}+1\mathrm{hw}$，GP 神力！，发现机房电脑巨抽象且不会重置，配置了一会环境（包括物理环境，你那键盘架子咋还爆掉了啊，桌面上咋那么多杂物垃圾啊），摸了会鱼。中午去食堂吃饭，$5$ 个 ss 的用一个饭卡，点了十碟肠粉和一份薯条，$-77\mathrm{r}$。下午不讲课不测试，补了 $6$ 号的题。晚上测试。

T1

简要题意：$T\le 2,000$ 组数据，已知 $A_1,B_1,A_2,B_2,N\le {10}^8$，求 $x$ 满足 $0\le x\le N$ 且 $\lfloor \frac{A_1}{x}\rfloor +B_1=\lfloor \frac{A_2}{x}\rfloor +B_2$ 的个数。

解析：很简单的整除分块……把 $\frac{A_i}{x}$ 的两个整除分块序列打出来，差为 $B_1-B_2$ 的显然就是答案。

纯人机，我用 STL 把两组整除分块的结果给存了下来，最后再一起算……大数据不能用 STL，能直接算出来的为什么要存，爆挂 ${60}^{\prime }$。

T2

简要题意：$T\le {10}^5$ 组数据，给定 $X,N,M\le {10}^{18}$，求 $x,y$ 满足 $0\le x\le N,0\le y\le M$，且执行若干次 $x\leftarrow x+y,y\leftarrow x+y$ 后，$x=X$。

解析：首先手玩，易得每一组 $x$ 和 $y$ 的系数构成 $f_1\leftarrow 1,f_2\leftarrow 1,f_i\leftarrow f_{i-1}+f_{i-2}$ 的斐波那契数列。

设存在一组符合题意的答案 $(x,y)$，这组答案经过 $c$ 轮操作后满足题意，$x_c=p$，$y_c=p+q$。易得 $p=X$。

$x_{c-1}=p-q,y_{c-1}=q$。

$x_{c-2}=2p-3q,y_{c-2}=2q-p$。

$\dots$

$x_{c-k}=f_{2k-1}p-f_{2k}q,y_{c-k}=f_{2k-1}q-f_{2k-2}p$

由题目 $x,y$ 的范围限制：

$$\{\begin{array}{c}0\le f_{2k-1}p-f_{2k}q\le N\\ 0\le f_{2k-1}q-f_{2k-2}p\le M\end{array}$$

只有 $q$ 是未知数，解这两个不等式，解出 $q$ 的取值范围，包含的整数个数就是答案。

$$a\leftarrow f_{2k-1},b\leftarrow f_{2k},c\leftarrow f_{2k-1},d\leftarrow f_{2k-2}$$$$max(\frac{ap-n}{b},\frac{dp}{c})\le q\le min(\frac{ap}{b},\frac{dp+m}{c})$$

$-1$ 再除再 $+1$ 可以代替向上取整，避免精度问题。

T3 AT_joisc2014_e 水筒

解析：由 P1967 [NOIP2013 提高组] 货车运输 的思路，用最小生成树 + LCA 做，问题在于怎么建图。

由于路径的性质，可以贪心如果存在路径 $x\to y\to z$，且 $dis(x,y),dis(y,z)<dis(x,z)$，它一定会先去 $y$，所以可以用多源 BFS，每个安全点扩展的一定会是一个连通块，连通块和相邻的连通块的就连边，这样最多会连 $2mn$ 条边。

纯细节题，没想到怎么建图，超级大暴力拿 $0$ 分。改题经验：变量名不要写混，不要乱用 STL。

T4 P7363 [eJOI2020 Day2] Dots and Boxes

解析：根据题目的限制，形成的可操作的连通块全都是长度至少为 $2$ 的链和环（除四角有可能出现长度为 $1$ 的链）。

因此，只要先手在某条链或环上下了一笔，出现了一个只剩一笔就能填上的格子，后手就可以顺着这个格子，直接把这条链或环里的格子全部填上，自己成为下一轮的先手。

但显然还有方法让后手不使得自己成为下一轮的先手：后手填完整条链的大部分格子之后，留两个相邻格子给先手，先手只能一笔拿下两个格子，或者直接去操作下一轮，但都会成为下一轮的先手，对于环则需要四个格子。

但是如果有长度为 $2$ 的链，那么先手可以先画中间，让后手无法留两个格子，必须成为下一轮的先手。

所以，后手有两种选择：

• 拿下整条链的所有格子，自己变成先手。$(1)$

• 拿下 $-2$ 或 $-4$ 个格子，自己还是后手。$(2)$

设 $f_{i,j}$ 表示处理完前 $i$ 条链，前 $j$ 个环（链和环从大到小排好序）的答案（两人分数之差）。

链的情况：

$$f_{i,j}\leftarrow {-}^{\ast }max\{\begin{array}{ll}lin{k}_i+f_{i-1,j}& (1)\\ lin{k}_i{-}^{\ast \ast }4{-}^{\ast }{f}_{i-1,j}& (2)\wedge lin{k}_i\ge 3\end{array}$$

$\ast$：因为对于情况 $(1)$ 来说，当前状态和上一状态是不同方，一方的收益是另一方的相反数。而对于情况 $2$ 来说，是相同方，所以再弄一个负乘回来。

$\ast \ast$：是 $4$ 不是 $2$ 的原因是：一方失了 $2$ 个，另一方得了 $2$ 个，分差一共增大了 $4$。

环的情况也同理，不过环没有不可以“保留后手”的情况：

$$f_{i,j}\leftarrow -max\{\begin{array}{ll}ci{r}_j+f_{i,j-1}& (1)\\ ci{r}_j-8-f_{i-1,j}& (2)\end{array}$$

$2024/10/10$

早上六点五十起，七点多一点经过高三楼下还被值日老师抓了要登记（乐），说是七点二十到结果七点半过了不久高中的才早读完来给我们开门。白天没有讲课没有测试，补了昨晚前三题和 $7$ 号前两题（一边摸鱼一边补其实效率没多高……）。下午吃了 KFC，晚上测试。

T1 CF1375C Element Extermination

解析：玄学做法。以序列最后一个数为 $tmp$，向前扫一遍，若出现一个数 $a_i>tmp$ 且 $a_{i-1}>a_i$（它不能被消去）则无解。

完了不知道在干嘛做道黄题做了两个小时。

T2

简要题意：给定一棵 $n\le {10}^6$ 的树，问等分这棵树的方案树。

解析：首先易得等分成 $x$ 份最多只有一种分法。

对于叶子节点而言，一定存在一棵子树包含它，否则它不可能被分好组。考虑从叶子节点往上一块一块搜，统计子树大小 $sz$，如果出现 $s{z}_u=x$，那么这就是一部分，直接删去，$s{z}_u\leftarrow 0$，$u$ 上方的节点又成为了叶子节点。枚举 $n$ 的因数，总时间复杂度 $O(n\times \mathrm{约}\mathrm{数}\mathrm{个}\mathrm{数})$。

考虑优化，对于 $s{z}_u$，如果它的子树中删去了若干个 $x$ 使 $x\mid s{z}_u$，那么 $s{z}_u$ 加回这若干个 $x$ 一样还是 $x$ 的倍数，所以不需要将 $s{z}_v$ 清零。只需要跑一遍 DFS，将 $sz$ 用一个 $cnt$ 数组计数。如果 $x$ 满足 $\sum _{i=x}^{n}cn{t}_i[x\mid i]=\frac{n}{x}$，那么这就是一种合法的方案。

完了不知道在干嘛做两道题做了三个小时。

T3

简要题意：有 $n\le {10}^5$ 个数，每个数无限多个，数值是 $1\le v_i\le 100$，求有多少种方案取数，使得数的总和小于等于 $k\le {10}^9$。相同数值不同位置的数算不同的方案。

解析：观察到 $v_i$ 的数值很小，所以不一定要从 $n$ 转移，设 $cn{t}_i$ 表示数值为 $i$ 的钱币的个数，$f_i$ 表示使得数的总和等于 $i$ 的方案数，$f_0\leftarrow 1$：

$$f_i\leftarrow \sum _{j=1}^{100}(f_{i-j}\times cn{t}_j)$$

很明显可以矩阵加速，设 $A=\left[\begin{array}{ccccc}{f}_{i-99}& f_{i-98}& \dots & f_{i-1}& f_i\end{array}\right]$ 乘上矩阵 $B$ 转移得到 $C=\left[\begin{array}{ccccc}{f}_{i-98}& f_{i-97}& \dots & f_i& f_{i+1}\end{array}\right]$，对于 $f_{i-98}\sim f_i$ 的部分，直接从 $A$ 矩阵对应数乘 $1$ 转移即可，$f_{i+1}$ 则按照上面的转移式往 $B$ 矩阵里填 $cnt$ 就行了。

但是最后的答案是 $\sum _{i=0}^k{f}_i$，所以再在 $A$ 矩阵中插入一个不参与 $f_{i+1}$ 的转移的 $f_{i-100}$ 统计前缀和，每次把 $f_{i-100}$ 和 $f_{i-99}$ 加起来当前缀和用。所以答案是 $(A\times B^{k+100}{)}_{1,1}$。

矩阵乘法是竖着加起来的。

本来九点搞完两题摆烂了，九点半突然听到可以用矩阵乘，半个小时干出来了。

T4

简要题意：一个二维平面中有 $n$ 个竖直挡板，第 $i$ 个挡板的端点为 $(x_i,a_i),(x_i,b_i)$，挡板互不相交。每个人可以选一个位置 $(x,y)$ 作为起点，随意地左右走来走去（改变 $x$ 坐标），但都不会穿过挡板。现在任意撤走一块挡板，找出最多的人数，使得任意两个人都不会移动到同一 $x$ 坐标。$n\le 2\times {10}^5$，$a_i,b_i\le {10}^9$。

解析：显然首先要知道不同的活动空间，和这个活动空间拆除左挡板或右挡板时的活动范围。假设用 $[l_1,r_1,l_2,r_2]$ 描述一个人本来可以在 $[l_1,r_1]$ 范围内改变 $x$ 坐标，拆除左挡板后范围变成 $[l_2,r_1]$，拆除右挡板后变为 $[l_1,r_2]$。

这部分可以用 扫描线 解决，在 $y$ 轴上从 $x$ 往小到大跑扫描线，发现对于一个活动空间，影响的只有 $r_2$ 所在的线段和与 $r_2$ $y$ 坐标相同的左侧的三条线段。所以对于每一个 $y$ 轴上分割出来的线段，线段树里开一个数组存当前分割出来的线段上，最后的 $4$ 条线段，它们的 $x$ 坐标时多少。此外，还需记录一下一整段区间内，这 $4$ 条线段是否相同，如果相同。当有新线段更新时，如果有相同的，那么这就是一个活动区间，不用再往下递归，直接返回并打上懒标记（是的，这个还需要懒标记）。此外还有一个注意点，扫描线模版题中提到的这个问题：

如果有两段区间分别是 $(100,200)$，$(200,300)$，更新 $(100,200)$ 时会把第二个区间也给更新了。

对于本题并不存在，因为如果 $(100,200)$ 被堵住了那么 $(200,300)$ 中 $200$ 这个点也会被堵住，所以按正常线段树写即可。

处理出来这个区间之后考虑 DP，先将区间按 $r_2$ 从小到大排序，并对坐标离散化。设 $f_i$ 表示 $i$ 最大为 $r_2$ 最多能站多少人，$g_i$ 表示在 $f_i$ 的前提下 $r_1$ 最小是多少。首先 $f_i\leftarrow f_{i-1}$，$g_i\leftarrow g_{i-1}$，对于当前区间，如果 $g_{l_1}\le l_2$，即之前的状态就算右挡板拆了，也不会移动到当前区间把左挡板拆了的地方，那么就可以转移：$f_i\leftarrow f_{l_1}+1$，$g_i\leftarrow r_1$，对于状态中的最大最小非常好处理，不再赘述。

T5

简要题意：设 $G(n)=\prod _{i=1}^n(2i-1)$，特别的，$G(0)=0$，给定 $n,m,x\le 2^{30}$，求：

$$\sum _{i=0}^n\sum _{j=0}^{m}G(i\oplus j\oplus x)$$

你需要输出答案对 $2^{32}$ 取模后的结果。

解析：为了这题补了一堆课……

按位考虑，设 $solve(i,j,a,b)$ 表示 $n$ 最后 $a$ 位随便取，$m$ 最后 $b$ 位随便取，且 $n/m$ 的第 $a/b$（从低往高）位是 $1$ 的方案数。由于后 $a/b$ 位随便取，所以 $n/m$ 的第 $a/b$ 位最小理应是 $0$，$i/j$ 就分别是这种条件下的 $n/m$。

$\le n,m$ 不好处理，将 $n$ 和 $m$ 都加一，类似在二进制下数位 dp，$<n$ 的一个限制（不过我也不会……），按位考虑。

考虑如果只有 $i$ 最后 $a$ 位随便取，显然它异或上一个什么东西之后还是最后 $a$ 位随便取。假设 $i_{min},i_{max}$ 分别表示最后 $a$ 位全部取 $0/1$ 的 $i$，观察到可以用 $G(i_{min})+G(i_{min}+1)+\cdots +G(i_{max})$ 得到这一部分的答案。

接下来考虑加入 $j$ 最后 $b$ 位随便取的条件，不妨令 $a\ge b$（不满足的时候交换一下就行了），那么最后 $a$ 位随便异或上最后 $b$ 位随便再异或一个什么东西之后，还是最后 $a$ 位随便取，所以可以用 $G(j_{min})+G(j_{min}+1)+\cdots +G(j_{max})$，再乘上 $2^a$ 补上 $i$ 中的空缺部分。

枚举 $solve$ 可以在 $O({\log }^{2}n)$ 内解决，接着考虑怎么解决 $G$ 的区间和。

首先可以想到前缀和，因此问题变成怎么求 $\sum _{i=1}^{x}G(i)$。

设 $G_k(x)=\prod _{i=0}^x(2i+1)mod{2}^k$，即 $G_k(x)=G(x+1)\mathrm{mod}{2}^k$，其中令 $G_0(x)=1$：

$$G_{k+1}(x)=2x\times G_k(x-1)+G_{k+1}(x-1)$$$$G_{k+1}(x)-G_{k+1}(x-1)=2x\times G_k(x-1)$$

发现 $G_k(x)$ 是一个 $2k-2$ 次多项式，要求的 $\sum _{i=1}^{x}G(i)$ 就是 $f(x)=\sum _{i=0}^{x-1}{G}_{32}(i)$，$x$ 次多项式的和也是 $x$ 次多项式，所以 $f(x)$ 也是一个 $62$ 次多项式。

对于一个 $x$ 次多项式，只要知道其中 $x+1$ 项，就可以用 $O(x^2)$ 的时间复杂度用 拉格朗日插值法 求出来。而 $f_0\sim f_{62}$ 的值显然根据题目的定义两轮递推就能求出来，用拉格朗日插值求出来就能解决这一部分的问题了。

但是还没完，拉格朗日插值要用除法，这里有取模，要用逆元，扩欧爆空间，模数不是质数又用不了费马小定理……引入一种新的求逆元方法：欧拉定理。

首先，对于 $ab=1(\mathrm{mod}m)$，如果 $gcd(b,m)\ne 1$，那么其逆元不存在，所以先把 $b$ 中 $m$ 有的因子全部除掉，对于这一题就是把 $2$ 因子全部除掉。

欧拉定理的内容是：模 $2^n$ 下一个奇数的逆元 $y^{-1}$ 可以表示为 $y^{\phi (2^n)-1}mod{2}^n$。根据前世学习欧拉函数的记忆：

$\phi (1)=1$，若 $q$ 是质数且 $nmodq=0$，则 $\phi (nq)=q\phi (n)$。

递推可以得到 $\phi (2^n)-1=2^{n-1}-1$，所以这题求逆元的算法就长这样：

int inv(int x, int y) {
    while (!(y % 2) and y)
        y /= 2;
    return x * Pow(y, (1ll << 31) - 1) % mod;
}

有一题和这个很像（特别是前面关于 $solve$ 的想法）：P3791 普通数学题。另外，恭喜本题以 $2075$ Markdown 字符断档领先拿下最长题解奖，断档领先第二名（$10/18$ T3，$1200$ 字符）。

$2024/10/11$

早上点了 KFC 早餐，GJ 昨晚居然没锁门，直接就进机房了。上午补了 $7$ 号剩的两题，下午补了 $9$ 号剩的一题（太摆了……）。晚上测试，做了两题不会做，摸鱼两小时，顺便把 Tarjan，Kosaraju，欧拉路相关陈年知识的笔记草草地补了。

T1 AT_abc188_e [ABC188E] Peddler

解析：拓扑排序签到题。

BYD 题面没强调一定要交易，那组凸显出一定要交易的样例还被 GJ 删了，无敌了。

T2 CF1696E Placing Jinas

解析：哪里不会（有数）点哪里，发现每一个格子要点的次数构成一个斜着的杨辉三角，直接求和肯定 TLE，用横平竖直的格子视角观察这个斜着的杨辉三角，格子一行到第 $j$ 位的和等于下一行第 $j$ 位的数，手推一下用组合数求就好了，时间复杂度 $O(n)$。

T3 AT_joisc2017_c 手持ち花火 (Sparklers)

解析：最大值最小，可以想到二分。

二分出来之后，考虑从 $[k,k]$ 逐步扩张到 $[l_{cut},r_{cut}]$，意为 $[l_{cut},r_{cut}]$ 范围内的花火能够全部被点燃过一次，这个区间中的 $x$ 坐标都应该满足以下条件（$v$ 是速度，$t$ 是花火最长燃烧时间）：

$$2vt(r-l)\ge x_r-x_l$$

化简，得：

$$x_l-2vtl\ge x_r-2vtr$$

设 $a_i=x_i-2vti$，如果 $[l,r]$ 可以扩张到 $[i,r]$，那么有：

• $a_i\ge a_l$。

• $\mathrm{\forall }j\in [i,r-1]$，$a_j\ge a_r$。

向右扩张成 $[l,i]$ 同理：

• $a_i\le a_r$。

• $\mathrm{\forall }j\in [l+1,i]$，$a_j\le a_l$。

从 $k$ 往两侧即可得到最大的 $[l,r]\to [l_{cut},r_{cut}]$，显然 $a_{l_{cut}}$ 在 $k$ 的左侧 $a$ 数组中最大，而 $a_{r_{cut}}$ 在 $k$ 的右侧的 $a$ 数组中最小。但 $l_{cut}$ 和 $r_{cut}$ 不一定分别位于 $1/n$，所以还需要从 $[1,n]$ 缩回这个区间，看看能不能缩回这里。收缩的判断是同理的，但有些符号方向要变。如果既可以扩张又可以收缩，那么这个速度就是一种可行的方案。收缩的意义类似于 GJOJ 题解上的前缀方法把它倒着求。

话说这个题目背景画进漫画里是不是篝火晚会跳舞的存在（雾。

T4 CF526G Spiders Evil Plan

解析：选一条路径肯定选择两个叶子间的路径，如果选的路径数的两倍比叶子数还要多，那么直接输出整棵树的边权和。

先不考虑必须覆盖某个点的限制，假如以 $x$ 为根，选一条路径很容易想到应该选择两条没被选过最长链。

如果每次询问都这么跑一次，会 TLE。观察发现经过 $x$ 的一条最长路径，这条路径至少一个端点位于树的直径的一个端点上。

所以只需要以直径的两个端点为根，跑两个树剖就可以得到两棵树中，每条边属于的长链，全部加起来再排个序再稍微操作一下，就可以得到每条长链的长度，和每个节点所属长链的长度在这棵树中的长链长度的排名（以下简称为点的排名）。

接着考虑必须覆盖某个点的限制，设 $m{x}_i$ 表示前 $i$ 条最长链的链长总和，$de{p}_i$ 表示 $i$ 下方的最长链长度，经过前面的操作，这两个是已知量。如果这个点的排名比要选的链数（注意不是路径数，一条路径至少应由两条新链组成）还要小，那么直接不用管，选前 $(2y-1)$ 条链即可，答案为 $m{x}_{2y-1}$。

• 为什么是 $(2y-1)$ 条而不是 $2y$ 条呢？因为根是直径的端点，一定是一个叶子节点，叶子节点上的路径只能由 $1$ 条链组成。

否则有两种策略，第一种是不要当前第 $(2y-1)$ 小的链，换成 $x$ 所在的链。但是 $x$ 所在的链只有下方可以在树剖确认，上方不一定能直接连通到目前的连通块，那么用 LCA 的倍增法跳上去即可，答案为 $m{x}_{2y-2}+de{p}_x+len$，$len$ 是 $x$ 从上方跳到连通块的长度。

第二种是 $x$ 往上跳到连通块碰到的是 $u$ 点，然后 $u$ 这条链往下不要它原本后面的，接到 $x$ 这边，答案为：$m{x}_{2y-1}+de{p}_x+len-de{p}_u$。

码量巨大，我写了 $4\text{ KB}$，不过是黑题感觉比较合理。

Day $-13=2024/10/12$

早上学了个最简单的拉插，然后就补了一题有关拉插的（$10$ 号 T5），因为都不会，题解都看不懂……整个下午都在研究拉插那题的内涵写笔记……然后放学。

Day $-12=2024/10/13$

睡大觉，追大番，抽大机。

晚七点，回学校，摸大鱼。

回学校盯真发现 $10$ 号 T5 漏看了什么不得了的东西，笔记有地方在瞎编，还有各种影响理解的奇葩笔误，重新改了一下，然后把不想写的 $9/28$ T1 的笔记给补了，然后学习扫描线，因为前面摸鱼摸太多加上洛谷爆了一会，写完扫描线笔记就差不多到点下班了。

Day $-11=2024/10/14$

逆天 $10$ 号 T4 细节一堆调了一早上，下午调 $11$ 号 T3。晚上测试有点难，太菜所以一题不会做。今天 nht 来了，他自己一个人一个宿舍（乐。

T1

简要题意：一个 $n\times m$ 的二维平面中（$n,m\le 300$），每个点都是空间和墙壁，相邻的空间视作同一个房间。房间内移动不消耗代价，直接传送移动消耗曼哈顿距离（两直角边的和）的代价，给定起点坐标，定义最大代价为最多只经过一次传送到达目的地的代价。请问对于图中每一个点，从起点出发且不超过最大代价最多可以传送多少次？同一个房间内不能传送。

解析：假设 $n,m$ 同阶，则最大可接受的时间复杂度是 $O(n^3)$。

第一步，求出每个点属于哪个房间，一遍 $O(n^2)$ dfs 即可。

第二步，求出从起点到每个房间的最大代价 $m{x}_u$，由于只能用一次传送，所以可以 $O(n^2)$ bfs，就算遇到房间也继续计算代价，但每个房间的代价只计算第一个碰到的点即可。

第三步，建图，可以证明如果两个点之间有连线，且这两个点组成的矩形内（包括边上）还有其他空间，那么显然可以从起点跳到那个空间再跳到终点，这条连线不优。这种组成矩形的问题可以用单调栈求，但单调栈对处理恰好矩形边上有两个点（起点和终点）的问题并不好用，所以考虑换一种方法。从上往下考虑，设 $lo{w}_x$ 表示 $(i,x)$ 及以上最下方的空间的 $i$ 坐标，对于点 $(i,j)$，如果它能和 $(lo{w}_x,x)$ 连边，那必然满足 $lo{w}_x>lo{w}_{[x+1,j-1]}$ 或 $lo{w}_x>lo{w}_{j+1,x-1}$，如果在上述范围内出现了 $lo{w}_k\le lo{w}_x$，那么显然组成的矩形中包含 $(lo{w}_k,k)$。这样建图最多是 $n^2$ 条边，且时间复杂度是 $O(n^3)$。

第四步，DP 求答案。设 $f_{i,j}$ 表示跳到第 $i$ 个房间传送 $j$ 次的最短距离，初始时 $f_{s,0}\leftarrow 0$，$f_{i,j}\leftarrow \mathrm{\infty }$：

$$f_{u,j}\leftarrow min\{f_{v,j-1}+w\}$$

找到最大的 $j$，使得 $f_{u,j}\le m{x}_u$，则 $j$ 就是房间 $u$ 的答案

看步骤挺简单代码要写 $4\mathrm{KB}$。

T2 CF1310E Strange Function

解析：对于 $k=1$ 的情况，就是 $10$ 号 T3，由于 $n$ 很小，$O(n^2)$ 可过，所以不需要矩阵加速，DP 即可。

对于 $k=2$ 的情况，将序列 $C=f(A)=\{c_1,c_2,\dots ,c_m\}$ 从大到小排序，则有 $|A|=\sum _{i=1}^{m}i{c}_i\le n$，差分，对每个数减去 $c_m$，再对 $[1,m-1]$ 的数减去 $c_{m-1}$，以此类推，问题转换为求 $\sum _{i=1}^m{c}_i\times \frac{i(i+1)}{2}\le n$ 的 $c$ 的方案数，同上 DP 即可。

当 $k=3$ 时，最终序列的总和只剩 $64$ 了，$64$ 的划分数只有 ${10}^7$ 级别，但是爆搜不剪枝也不一定过，故 $k=3$ 考虑爆搜打表。

当 $k\ge 4$ 时，总和只剩 $24$ 了，爆搜 + 暴力判断长度是否超过 $n$ 即可。

暴力判断时，应尽量将每一层较大的数放在前面，这样可以使得最终的序列尽量短。

T3

简要题意：构造一个只由 $\mathtt{\text{r}}$，$\mathtt{\text{y}}$，$\mathtt{\text{x}}$ 构成的矩阵，使得横着，竖着斜着，正着，反着连续出现的 $\mathtt{\text{ryx}}$ 的个数恰好有 $n\le 2222$ 个。构造的矩阵大小不能超过 $40$ 行或 $40$ 列。

解析：很容易想到每一行都填 $\mathtt{\text{ryxyryxyr}}\dots$ 的贪心策略，这样子横着的 $\mathtt{\text{ryx}}$ 一行至多有 $19$ 个，$40$ 行就是 $760$ 个。竖着的没有，斜着的从第三行开始，每一行会贡献出 $38$ 个，$38$ 行就是 $1,444$ 个。

相加得到 $2,204$ 个，还差 $18$ 个咋办呢？观察到这种填行策略第 $37\sim 40$ 位填的是 $\mathtt{\text{ryxy}}$，即每一行的第 $40$ 位都没有任何贡献，这样子可以竖着填 $\mathtt{\text{ryxyryxyr}}\dots$，再增加 $19$ 个，这样就有 $2223$ 个了。

先把表填满，接着从 $\mathtt{\text{x}}$ 的角度考虑，计算出每个 $\mathtt{\text{x}}$ 能贡献多少个 $\mathtt{\text{ryx}}$，对贡献 $p$ 个的坐标放进动态数组 $ve{c}_p$ 里，要求 $n$ 个 $\mathtt{\text{ryx}}$ 就是要从 $vec$ 中拿出若干个坐标，使得拿出的坐标贡献的总和等于 $2223-n$，这部分很好做，考虑怎么求 $vec$ 数组。

其实也很简单，共有如下几种情况：

• 位于第 $40$ 列。

  • 位于第 $39$ 行：这个 $\mathtt{\text{x}}$ 无法和下面的 $\mathtt{\text{y}}$ 组成答案，只能贡献 $1$ 个。

  • 其他情况：这个 $\mathtt{\text{x}}$ 和上下的组成答案，贡献 $2$ 个。

• 其他情况。

  • 位于第 $39$ 列

    • 位于第 $1,2$ 行：和左边，左下，贡献 $2$ 个。

    • 位于第 $39,40$ 行：和左边，左上，贡献 $2$ 个。

    • 其他情况：和左上：左边和左下，贡献 $3$ 个。

  • 其他情况。

    • 位于第 $1,2$ 行：和左边，左下，右下，右边，贡献 $4$ 个。

    • 位于第 $39,40$ 行：和左上，左边，右边，右上，$4$ 个。

    • 其他情况：$6$ 个方向：$6$ 个。

这个方法码量应该算比较少了，$1.9\mathrm{KB}$ $66$ 行，某 dalao 考场打了 $200$ 行……

考场算错数（没算出来 $2223$）直接挂到只剩 $20$ 分……

T4

简要题意：有排列 $\{s_n\}$，定义 $g(k,i)=\underset{j=i}{\overset{i+k-1}{min}}(s_j)$，$G(k)=\underset{i=1}{\overset{n-k+1}{max}}g(k,i)$。给定 $G$ 和 $n$，求不同的 $s$ 的个数，对 $998,244,353$ 取模。

解析：考虑将 $n\sim 1$ 从大到小用类似排列 dp 的方式加入，如果 $G(L)=i$，那么有加入数 $i$ 之前，最大的连续段小于 $L$（否则 $G(L)$ 会是一个已经加入的数）；加入数 $i$ 之后，最大的连续段长度大于等于 $L$。

先求出 $m{x}_i$ 表示对于 $i$，上述的 $L$ 值应该是多少，然后用 dfs 求出所有的符合条件的连续段的情况，共有 $50$ 的划分数，也就是 $2\times {10}^5$ 左右种情况。每种情况最多只有 $50$ 个数，所以可以直接把详细情况全部存起来。需要注意的是当拆分 / 合并后，权值会 $-1$ / $+1$。

然后考虑 dp，当连续段个数为 $1$ 时，是答案，所以从连续段个数多的开始 dp，每次将这组连续段的某个段拆成两部分，map 判断是否存在新的一组连续段，存在即转移。

$$f_u\leftarrow \sum f_v$$

Day $-10=2024/10/15$

早上补 $11$ 号 T4。中午叫外卖先在科学楼和大门连线的中点（？）被下班的 gj 抓了，然后在丰巢被也吃外卖的 zsq 抓了，接着被门口保安拿下了（还好有 zsq 帮忙开脱），最后在宿舍上楼梯又被宿管发现了……下午补 $14$ 号 T2，T3。晚上不测试，但发现剩下两题一题不会实现另一题看不懂题解。八点开始搞 T1 搞到下课，笔记明天写。

Day $-9=2024/10/16$

早上成功把之前欠的题给补完了（翻译：补了一题）。中午给自己买了生日礼物（迫真）。下午摆了一会，做了一道 ABC375G（笔记）。晚上摸鱼，把我用了快一年的洛谷 R☆ 主题换成 やなみ 了。

Day $-8=2024/10/17$

早上洛谷刷了几题，复习了一些算法，把 GDKOI 的时候想学的凸包给学了（不过忘记为啥要学那玩意了）。下午打 ABC369（笔记）找 J 组手感，挺简单的一场，有生之年我能 $90\min$ AK ABC。晚上终于有 GJOJ 的测试，这都几天没测了，但我不知道在宿舍玩到六点半多（测试六点回班，不测试任意）。

T1

简要题意：在一个长为 $n\le 2\times {10}^5$ 的数中，选取两个连续的位，将它们相加再将和放回这个位置，当数只剩一位的时候操作停止，求最多操作次数。

解析：诈骗题，只需要从左一路往右，能加则加，就能通过。那些“先合后面的大数更优”，算一下或者随便举几个例子，就会发现都和从左往右加是等价的。

T2

简要题意：有 $n\times m$（$n,m\le {10}^3$）个点按顺序排列，每个点和它上下左右的四个点连边，求它直径长度恰好为 $t$ 的生成树，输出每条边的起点坐标和终点坐标。

解析：先判断无解的情况。容易想到直径最短的情况是横着连，然后再竖着从中间连一整条。但是列数的奇偶会影响这一个值，关注到在这种情况下行数不会影响这个值，所以先尽量将列数变为奇数（swap 一下）。

手玩可得列数奇数时，直径最小是 $n+m-2$，否则是 $n+m-1$。无论列数奇偶，直径最大都是 $nm-1$。

接着采取 $14$ 号 T3 同款思路，奇数“行间”（两行之间的空间，从上往下编号）的边向左移一格能增加 $2$ 的直径长度，偶数的则是向右移一格能增加 $2$ 的直径长度，一直加就行。

但是可能会还差一个，把最后一行的逆时针旋转左下角的横边，或者顺时针旋转右下角的横边一下就行了。如果这一行中间那一条是往右的就旋转左下角的，否则旋转右下角的。

这是旋转左下角的情况，将蓝色往下旋转：

码量 $2\mathrm{KB}$。

这样写就可以在 GJOJ 中的随机数据中拿下 $187/200$ 个点的好成绩，这个方案错在哪里了呢？错了一堆。

如上图所示，设此时 $n=3,m=5,t=13$，显然还差 $1$，按照上面的思路，要是旋转左下角，就会：

红边是要走的，咋就打断了呢？所以这个时候选择将最后一行的竖线再左 / 右一格，增加 $2$ 距离，然后旋转最后一行的一个而不是倒数第二行的来减掉 $1$ 距离。

这种情况不能乱用，当且仅当倒数第二行的竖线被移动到尽头了才能用，否则答案会错。

接下来就是毒瘤情况：$2$ 行的，我没想到任何一种方案能既满足 $2$ 行又满足其它行的。

比如这种情况，如果它上面还有更多行，它肯定是从 $(1,5)$ 走进来的，而这里可以走 $(2,1)$ 出发，虽然图中情况不影响答案，但实际上会影响。

所以考虑先弄成弓字形，然后加加减减。

然后又会发现漏掉了工字形和 $1$ 字形的情况，特判。

……

码量变成 $4\mathrm{KB}$。

T3

简要题意：给定一个只有 $0/1$，与或异或的位运算表达式，每一步运算都会有括号规定运算顺序（即不会出现类似 $a|b|c$ 的情况，会给出 $(a|b)|c$）。现在有些符号是 $\mathtt{\text{\#}}$ 意为未知，有些数字是 $\mathtt{\text{?}}$ 意为未知，求有多少种填 $\mathtt{\text{\#}}$ 和 $\mathtt{\text{?}}$ 的方案使得表达式值为 $1$。

解析：又是我又爱又恨表达式题，但是这个挺简单。

由于已经规定运算顺序，所以可以直接对每一层拆成左右两半递归。用 $cn{t}_0$ 和 $cn{t}_1$ 表示这一层取 $0/1$ 的方案书，递归到最底层时 $0$ 就 $cn{t}_0\leftarrow 1$，$1$ 就 $cn{t}_1\leftarrow 1$，$\mathtt{\text{?}}$ 就两个都弄上。然后合并左右两边的答案就用位运算的定义合并就行了（比如与就左边 $1$ 的方案乘上右边 $1$ 的方案），如果符号未知，就三种运算都转移一次就行了。

是码量低达 $2.4\mathrm{KB}$ 的优质表达式题目。

T4 AT_cf16_exhibition_final_e Water Distribution

解析：操作两个点一定是只操作一次最优，而操作成一棵树肯定比操作成一张有环的图更优（如果成环了，某个点先减水后加水，血亏；如果成图了，汇在一起的地方消耗了更多的代价）。

因此操作的路径能够在图上组成一棵棵树，先处理出每棵树的答案。

$n$ 很小考虑直接暴力枚举点集，设 $f_s$ 表示点集状态为 $s$ 时，答案的最大值。答案的上界是 $(\sum _{i\in s}{a}_i-\sum _{u\in s\wedge v\in s}dis(u,v))÷\mathrm{popcount}(s)$，手玩发现这个值一定是可以达到的，被除式的减式可以用最小生成树统计。其他都可以直接统计。这一部分时间复杂度是 $O(2^n\times n\log n)$ 的。

接着考虑整张图的答案，整张图的答案由若干个连通块组成，所以设 $g_s$ 表示点集状态为 $s$ 时的答案，可以由它的子集转移 $t$ 过来：

$$g_s=\underset{t\subseteq s}{max}(g_s,min(f_t,g_{s\oplus t}))$$

答案是 $g_{2^n-1}$，枚举子集的时间复杂度是 $O(3^n)$，代码见 $7$ 号 T4。

Day $-7=2024/10/18$

早上补题，下午摸鱼，晚上测试，一题不会。心情不好，打完暴力，写抽象小作文。

T1

简要题意：给出 $n$ 个数 $A_{1\dots n}$，迭代一次 $i$ 可以使 $A_i^{\prime }\leftarrow \lceil \frac{A_i}{2}\rceil +k$，$q$ 次询问，每次询问求出所有数迭代 $m$ 次后，$A$ 序列的总和。$n,q\le {10}^5$，$A_i,m,k\le {10}^9$

解析：由 $k=0$ 推广，发现任意一个数列经过 ${\log }_2(k)$ 次操作后，答案就不变了，枚举个 $50$ 项输出即可。

T2

简要题意：有一个字母 $s_0$，每天它的一个子序列 $t_{2i-1}$ 变成 $t_{2i}$，在第 $m\le {10}^5$ 天时，$s_0$ 变成了序列 $s_1$，但现在 $t$ 数组被打乱了，已知 $s_1$，求 $s_0$。

解析：由 $t_i$ 的长度均为 $1$ 推广，发现答案一定是在所有字母中出现奇数个数的那个，数组计数输出即可。

证明：$t$ 中的每个字母都是加入，删除，加入，删除，最后生成了 $s_1$，将他们全部删除，这样子每个字母都应该在 $t$ 和 $s_1$ 中总共出现了偶数次，但 $s_0$ 不需要加入这一操作，只需要删除，所以 $s_0$ 的字母只出现了奇数次。

T3

简要题意：有一个 $n\le 38$ 个正整数的序列 $a$，给出 $m$ 对关系，第 $i$ 对关系表示 $\mathrm{lcm}(a_{x_i},a_{y_i})=b_i$，其中 $b_i$ 以 $\prod _{j=1}^k{c}_{i,j}{p}_j$ 的形式给出，$p_i$ 是从小到大的第 $i$ 个质数，$k\le 8$。求不同的 $a$ 的方案数。

解析：发现并不关心这些数的数值，每对关系的实际意义就是 $max(d_{x_i,j},d_{y_i,j})=c_{i,j}$，$d$ 表示 $a_{x_i}$ 中 $j$ 的质因子的个数。

发现不同的 $j$ 互不干扰，所以对 $k$ 个质因数分开处理，最后将每种质因数的方案数直接乘起来就好了。

容易想到 $x_i$ 向 $y_i$ 连一条边权为 $c_i$ 的边，处理出每个点的 $limi{t}_i$ 表示这个点能取到的最大值（即和它连的边中的最小值）。

如果有连边 $(i,j,w)$，$limi{t}_i<w\wedge limi{t}_j<w$，那无论怎么取 $i,j$ 也达不到这条边的要求，输出没有解。

如果某个点没有限制要求，且不是无解，这个点取啥都行，输出无数解。

然后处理出每个点的 $un{d}_i$ 表示这个点不取最大值，哪些点必须要取的点集状态。

• 如果有连边 $(i,j,w)$，且 $limi{t}_j<w$，那么 $i$ 不能不取最大值，$un{d}_i$ 里包含上 $i$。

• 如果有连边 $(i,j,w)$，且 $limi{t}_i=limi{t}_j$，容易证明两个点的 $limit$ 都等于 $w$（不可能大于，小于就无解），这时如果一个不取最大值，另一个就要取最大值。

接着开始算答案，由于 $n$ 有点大，$2^{38}$ 肯定炸，考虑拆成两半做。

设 $f_s$ 表示其中一半的点集中，不取最大值的点为 $1$，取最大值的点为 $0$ 的方案数，显然方案数是 $\prod _{i\subseteq s}limi{t}_i$。但这个状态不一定合法，维护一个 $mu{s}_s$ 将 $\mathrm{\forall }i\subseteq s$，$un{d}_i$ 或起来，这些点都要取最大值。如果有个点又要取最大值，又要不取最大值（即 $s\mathtt{\text{\&}}mu{s}_s\ne 0$），这个状态不合法。

两半都做完一遍之后，对于左半，高维前缀和合并；对于右半，直接一边枚举一边统计答案，如果右边选了 $s$ 点集，左边就可以选 $2^l-1\oplus mu{s}_s$，即除了不能选的点都选（因为已经高维前缀和合并答案了），两边相乘，再将所有的 $s$ 的这种情况加起来，就是一个质因子的答案。

所有质因子的答案相乘即可。

T4

待补。

Day $-6=2024/10/19$

七点整没走被宿管怒骂，但是我们七点二十才上课且不用早读，有个宿管是 lyt 他爸，他说肯定是我们半夜抽手机，严查，不过我觉得十点四十关灯睡到七点也不算多。然后是鲲鹏班的今天来上课了，在 $2$ 室和 $3$ 室反复横跳。

中午 cjrawa 没带饭票，我把饭票给他，我刷饭卡。石中饭卡在食堂好像有单笔不得超过 $22\mathrm{r}$ 的限额，结果我点了 $22.5$ 的菜，作为高贵的 NFC 用户用电子设备刷，结果饭堂大叔认为就是电子设备刷不了，我还给他看了能刷出余额 $1000$ 多……被后面一群等着打饭的学姐围观。

早上测试接着挂大分，挂了 ${130}^{\prime }+$。下午解放。

晚上打了 ABC，花二十分钟多一点把前五道水题切了，然后摆烂。

T1 [ABC103C] Modulo Summation

解析：易得 $x$ 取所有数的公倍数减一时，式子有最大值，为 $\sum _{i=1}^n(a_i-1)$。

T2 P3106 [USACO14OPEN] Dueling GPSs S

解析：对两台 GPS 都跑一次倒着的最短路，设 $f_i$ 表示到达 $i$ 点时，最小的报错数。如果边 $(u,v)$ 不是任何一台 GPS 通往 $n$ 点的最短路，$f_v\leftarrow f_u+2$；如果是其中一台的，$f_v\leftarrow f_u+1$；如果都是，$f_v\leftarrow f_u$。

某个点通往 $n$ 点的最短路和 $f$ 都能用 Dijkstra 维护，跑三遍即可。

你永远无法理解一个人为什么要跑两遍 Dijkstra 然后跑一个爆搜，挂 ${70}^{\prime }$。

T3 CF920F SUM and REPLACE

解析：这种类型的题太典了，本质上来说，昨天的 T1 也是这种题。

先线性筛预处理出 $d$，显然一个数如果一直 $x\leftarrow d(x)$，不用几次它就会永远变成 $1$ 或 $2$，因此用并查集维护，是 $1$ 或 $2$ 的直接跳过就好了，跳过的写法具体见下附代码。因为收缩的速度很快，所以不是 $1$ 或 $2$ 的就暴力修改，对于区间和维护就用树状数组即可。

关于如何用线性筛求出 $d$：

• 设 $cn{t}_i$ 表示数 $i$ 最小的质因子在 $i$ 中出现的次数，如 $cn{t}_8=3$（$8=2^3$），$cn{t}_{1}2=2$（$12=2^2\times 3^1$）。

• 设 $x=i\times prim{e}_j$（即由 $i$ 推到 $x$），如果 $i\nmid prim{e}_j$，$cn{t}_x\leftarrow 1$，$d_x\leftarrow 2d_i$

  • 因为根据线性筛的筛法，每个数只会被自己的最小质因子筛掉，所以 $x\mid prim{e}_j$ 且 $i$ 的最小质因子 $\ge prim{e}_j$，结合上面条件就可以知道 $i$ 的最小质因子不等于，即大于 $prim{e}_j$，所以 $x$ 目前只有 $prim{e}_j$ 这一个最小质因子，$cn{t}_x\leftarrow 1$。

  • $i$ 的每一个约数都是 $x$ 的约数，每一个 $i$ 的约数乘上 $prim{e}_j$ 也是 $x$ 的约数。而 $i\nmid prim{e}_j$ 说明不存在一对 $i$ 的约数 $p,q$，能使得 $q=p\times prim{e}_j$，因此上面提到的两种 $x$ 的约数不会重复，直接乘 $d_x\leftarrow 2d_i$ 即可。

• 如果 $i\mid prim{e}_j$，那么 $cn{t}_x\leftarrow cn{t}_i+1$，$d_x\leftarrow d_i÷(cn{t}_i+1)\times (cn{t}_x+1)$。

  • 同上面的推导方法，根据上面的条件，$i$ 和 $x$ 的最小质因子都是 $prim{e}_j$，转移即可。

  • 这个时候会有重复的情况，只需要运用前一种情况求 $d$ 的思路，先除去 $cn{t}_i$ 所代表的质因数在 $i$ 的约数中的贡献再乘回去即可。

这是并查集的代码：

for (int j = x; j <= y;) {
    // update...
    if (a[j] <= 2)
        un(j, j + 1);
        // 注意是 j 指向 j + 1，保证 gf 出来的一定是还需要修改的数
    do {
        j = gf(j + 1);
    } while (j <= y and a[j] <= 2);
    // 跳
}

GJOJ 甚至是 $4\mathrm{s}$ 时限，用根号级别的求 $d$ 都能干过去。但是不开 long long 挂 ${60}^{\prime }$。

T4

简要题意：有一个 $n\le 500$ 个点的简单无向图，任意挑选一个点出发走不重复的五条边，求总方案数。

解析：由于 $n$ 很小，所以任何一个三次方的算法都是可以通过的，所以考虑将枚举五条边，改成枚举五条边中间的边，再计算两个端点向外走两步的方案数，容斥掉不合法的方案数，再减去三元环和四元环重复的方案即可。

设点 $u$ 往外走两步的方案数是 $g_u$，每个点的度数是 $d{g}_i$，那么如果有边 $u,v$，则 $g_u\leftarrow d{g}_v-1$，意为减去走回自己的这条边。

接下来是第二步，枚举五条边中间的边，设这条边是 $(u,v)$，先算出总数是 $g_u{g}_v$，接着有可能会有这种不合法方案也被计算进去：

所以要减去 $g_u(d{g}_u-1)$ 和 $g_v(d{g}_v-1)$，根据容斥，再加回去 $(d{g}_u-1)(d{g}_v-1)$。

接着算三元环的情况，由于三元环只有三个点，暴力枚举即可，对于一个三元环，它有以下几种的不合法方案：

上面的三种和 $d{g}_{i_1}$ 有关，所以这三种的方案数是 $3(d{g}_{i_1}-2)$，下面一种和 $d{g}_{i_1}$ 无关，不合法的方案数是 $1$。

最后算四元环的情况，枚举四元环可以枚举它的对角线，然后将和对角线的两个端点都有边相连的点的个数统计起来 $cnt$，四元环的个数就是不同的对数，$cnt(cnt-1)$。

发现四元环只有上面这一种不合法的方案，因此每个四元环减去四就行了，而每个四元环有两条对角线，正反都算就是每个四元环都会被算四次，所以直接减去 $cnt(cnt-1)$ 即可。

Day $-5=2024/10/20$

睡到十点多，早上打 PUBG 发现没手感，然后看了一下午漫画，把剩下 $10$ 本高木同学看完了。

晚上六点二十出门回学校，结果黄岐大桥日常塞车，$5\mathrm{km}$ 用了 $1\mathrm{h}$。

如此颓废，何以 CSP。调昨天 T4 还调不出来，直接妈妈生的。

Day $-4=2024/10/21$

T1

简要题意：给定两个长度为 $n\le {10}^5$ 的序列 $a,b$，$b_i$ 表示将 $a_i$ 增加 $1$ 的最小代价，求将 $a$ 序列全部不同的代价。$a_i,b_i\le {10}^9$。

解析：可以想到每次给一个数加一，对于相同的数，一定取 $b$ 小的往上拉。所以可以将所有数按 $b$ 从大到小排序，用并查集维护这个位置是否被先前的数占了，如果被占了，就把它一路往上拉，拉它一定比拉先前进来的数要优。并查集可以用 unordered_map，可以证明并查集中一定最多有 $n$ 项，所以空间复杂度正确。

T2

简要题意：定义最小生成树是指边权二进制或下和最小的生成树。给出一张 $n\le {10}^5$ 个点的图，$q\le {10}^5$ 次互不干扰的询问，每次询问在 $(u,v)$ 之间添加一条边权为 $0$ 的边，求最小生成树。

解析：考虑拆位做，枚举每一位是选 $1$ 还是选 $0$。

具体来说，先假定这一位选 $0$，对于这一位是 $0$ 的边跑一次题意的最小生成树，如果可以构成一棵树，那么这一位就可以选 $0$，否则这一位只能选 $1$。

每次询问都跑一遍肯定超时，但是发现一条 $0$ 边如果可以将第 $x$ 位从 $1$ 变成 $0$，那么说明原图这一位是 $0$ 的时候，是两个连通块，且恰好可以被这一条新加入的边连接起来。

如果第 $x$ 位是可以划分成两个连通块的，对两个连通块分别进行一次 $x\to 0$ 位选 $0/1$ 的最小生成树即可。

发现这个操作执行了很多次，可以用个结构体就不用反复清零或开一堆数组了。

询问的时候，从高到低，如果第 $x$ 位在原图的答案上是 $1$，但是第 $x$ 位取 $0$ 被划分成了两个连通块，恰好新增边的两个端点位于两个连通块（并查集维护），这一位就能变成 $0$，贪心直接输出这一位变成 $0$ 后的答案即可。

T3

简要题意：给定 $n\le {10}^5$ 个字符串，每个字符串权值为 $0$，$q\le {10}^5$ 次操作。第一种将前缀与指定字符串的指定前缀相同的字符串，权值全部加 $x$。第二种建立一个新字符串，由在指定字符串的指定前缀后接上指定字符串构成。第三种求第 $x$ 个字符串的权值。

解析：伪做法，可以卡到 $O(qL)$。

直接用一棵字典树维护，加权值就直接加在前缀的末尾，求答案的时候统计整个字符串的路径上的所有权值。但是这样会有问题，之前加的权值不属于一个新建的字符串，所以新建字符串的时候统计一下这条路径上之前的权值，求答案时减去这个值即可。

期望复杂度 $O(q\sqrt{L})$。

T4 CF1028H Make Square

解析：先将每个数的质因子个数 $mod2$，因为成对的质因子一定能直接构成完全平方数，不需要考虑。

这样子每个数的质因数最多只有 $7$ 个，每个数的约数最多只有 $2^7$ 个，全部存下来可以暴力枚举。

处理出数据范围内，每个数除去成对质因子后，剩下的质因数个数，设 $f_i$ 表示 $i$ 经过操作后剩下的质因子个数。

对于一次询问 $[l,r]$，答案显然是 $\underset{x\in [l,r]\wedge y\in [l,r]}{min}\{f_{a_x}+f_{a_y}-2f_{gcd(a_x,a_y)}\}$。

发现答案最大只有 $14$，所以可以将询问区间离线下来，按右端点从小到大处理。在右端点相同时，答案随左端点增加而减小。所以设 $h_i$ 表示当前右端点答案为 $i$ 时，左端点的最大值，$g_{i,j}$ 表示满足 $i\mid a_x$ 且 $f_{a_x}=j$ 的 $x$ 的最大值。枚举所有的 $gcd(a_x,a_y)$，即枚举 $d$ 满足 $d\mid x\wedge d\mid y$。

对于当前点的处理，$f_{a_i}-2f_d$ 这一部分是已知的，$f$ 数组不超过 $7$，直接枚举 $f_x$，那么有 $h_{i+f_{a_i}-2f_d}=max\{g_{d,i}\}$，在维护一下 $g$ 数组，$g_{d,f_{a_i}}=i$ 即可。

最后求答案，找到最大的 $l^{\prime }$ 满足 $h_i\ge l$，这个询问的答案就是 $i$。

Day $-3=2024/10/22$

五楼电脑室清场了，下午去二楼五室摸鱼。晚上摸了没一会就被拉去当内阁布置考场。

Day $-2=2024/10/23$

把题补到只差一题了，然后早上复习了悬线法，Tarjan，Kosaraju 和 CDQ 分治。下午继续当内阁，晚上测试但是机智的 gj 不告诉我们 freopen 的文件名，于是我们所有人荣获 $0$ 分。

T1

简要题意：初始时有一个只有一个数，数值为 $1$ 的序列。给定 $n\le {10}^6$ 个操作，每个操作为 $1/-1/0$。$1$ 表示往序列里添加一个数 $1$，$-1$ 表示合并序列中的任意两个数，$0$ 表示可以执行以上两个任意一个操作。求序列最大平均值。

解析：合并的顺序不影响答案，影响答案的只有个数和总和，考虑能合则合，如果遇到某个 $-1$ 合不了，就把之前的一个 $0$ 吐出来当 $1$，维护即可。

T2

简要题意：$n\le {10}^5$ 个人，$m\le {10}^5$ 个地点，每个人有两个想去的地点。现在所有人两两结伴前往一个他们想去的地点，求落单的人数。

解析：很容易想到图论建模，先把每个人都随便丢去一个他们想去的地点，统计出当前每个地点的人数，然后把每个人想去的两个地点间连边，可以发现，一定存在方案使得一个连通块内的落单人数为 $0/1$，取决于连通块内人数对 $2$ 取模的值，遍历有多少个连通块内总人数是奇数个即可。

T3

简要题意：$n\le 4\times {10}^6$ 个数 $a_{1\dots n}$，$0\le a_i<2^{64}$，求 $\sum _{1\le i<j<k\le n}(a_i\oplus a_j)\vee a_k$。

解析：考虑按位处理，算出每一位的贡献，当处理到第 $i$ 个数第 $x$ 位时，统计出前面所有数第 $x$ 位是 $0/1$ 的个数 $c_{x,0/1}$。

如果当前这一位是 $1$，那么前面异或的两个数是什么都可以，方案数是 $(i-1)(i-2)÷2$

如果当前这一位是 $0$，那么前面异或的两个数必须一个 $1$ 一个 $0$，方案数是 $c_{x,0}{c}_{x,1}$。

方案数乘上 $2^x$ 就是这一位的贡献，全部加起来即可。

T4

简要题意：给定 $n\le 2\times {10}^5$ 个数，可以任选一位开始往后，在原序列中加上一个长度为 $m$，首项为 $c$，差为 $d$ 的等差序列，求第 $k$ 大数的最大值。

解析：考虑二分答案，二分出这个最大值后，判断是否有 $k$ 个数大于等于这个最大值。

设序列中原本就大于等于这个值的数有 $x$ 个，那么还需要找到 $k-x$ 个数经过操作后可以超过这个值。

对于每一个数，可以计算出它要大于等于这个值的话，等差序列第一个数的位置最左和最右可以是哪里，打上 $1$ 和 $-1$ 的差分标记。然后跑一遍前缀和，如果某个位置数大于等于 $k-x$，那么这个答案可行。

Day $-1=2024/10/24$

早上摸大鱼，补昨晚的题（都挺好写的）。下午摸鱼一小时 + 复习一小时。晚上测试，挂了那么久终于又自己场切两题了（不过还是很人机）。

T1

简要题意：求无向图中包含边数量最少的不同环的个数，点数小于等于 $3000$，边数小于等于 $6000$。

解析：从 ABC376D 中汲取经验，考虑以每个点为环的起点 / 终点，BFS 算出这个点到每个点的距离 $dis$ 和方案数 $f$，如果两个点相遇了，那么这就构成了一个环，$cn{t}_{di{s}_u+di{s}_v+1}\leftarrow f_u(f_v-[di{s}_v=di{s}_u+1])$ 统计起答案，为了方便计算，统一算 $di{s}_u\le di{s}_v$ 的。

然后发现每个环被算了二倍环中包含的点的个数次，除去即可。

小细节调了我两个钟。

T2

简要题意：$n_1\leftarrow (n_0^2+1)moda$，$n_2\leftarrow n_1+b$，$n_3\leftarrow n_{2}modc$，$a,b,c\le p\le {10}^5$，给定 $n_0,n_3,p$，求 $a,b,c$ 的方案数，并输出字典序的前 ${10}^5$ 种。

解析：对上脑电波了属于是，设 $f_i$ 表示 $i$ 且满足题意的 $c$ 的个数：

• $i<n_3$，$f_i\leftarrow 0$。

• $i=n_3$，$f_i\leftarrow p-n_3$。

• $i>n_3$，发现所有贡献出自 $i-n_3$ 的约数，暴力枚举并判断是否合法，一个一个加即可。

这一部分 $p\sqrt{p}$ 可求。

接着枚举 $a$，答案数为 $\sum _{i=n_1}^{n_1+p}{f}_i$，前缀和处理一下 $f_i$ 即可，算答案数的部分解决了。

输出前 ${10}^5$ 种，可以先用 vector $v_i$ 存下给 $f_i$ 贡献的数，然后暴力枚举上面那个区间，$b$ 就是 $i-n_1$，$c$ 就是 $v_i$ 中存的所有数。掐指一算时间复杂度 $p^2$，但跑得飞快，不用 $0.1\mathrm{s}$。

T3

简要题意：一个长度为 $n\le 1.5\times {10}^6$ 且只包含 $\mathtt{\text{a}}\sim \mathtt{\text{z}}$ 的字符串，$m\le {10}^5$ 次询问，求区间 $[l,r]$ 内两个不同字母交替出现的子串的最长长度，并输出这个子串的第一、二个字母。

解析：先处理出每个字母个数的前缀和和每个字母出现的位置，后者用 vector 存起来。对于每个位置，枚举每个字母，如果这个位置和这个位置的字母上一次出现的位置之间，枚举的字母出现过，那么这段区间“有答案性”就是 $1$，前缀和 $f$ 统计，这一部分时间复杂度 $O(26n)$。

接着处理询问，枚举由字母 $i,j$ 组成答案，假设 $i$ 第一次出现 $\ge l$ 的位置是 $ls$，最后一个 $\le r$ 的位置是 $rs$。那么长度就是 $2(f_{rs,j}-f_{ls,i})+1$，还需处理一下 $rs$ 后面有没有再出现 $j$。时间复杂度 $O({26}^{2}m)$。需要注意一些可以预处理的要提前预处理（比如求 $l$ 后的 $ls$），不然时间复杂度会再多一个 $\log$，超时。

T4

待补。

Day $0=2024/10/25$

停课的日子一下就过完了。早上摸鱼，中午睡完觉就起床收东西准备回石实，回家拿东西耽误了一会，最后四点半才到机房，调第三题。晚上 GJOJ 模拟赛没打。

本记录到此完结，共 $32859$ Markdown 字符。共有 $2$ 题没补，占集训总题数的 $3.84\mathrm{\%}$。