广东省队集训
dspt
·
2025-04-20 16:12:50
·
算法·理论
讲课只记录了上课讲的，网上能找到的题目。标 ? 的是我不会的。
怎么收藏比点赞多啊？
相信我会慢慢更新的！
Day 1
T1 最小生成树 | Multi-University Training 2022 Contest 3 Spanning Tree Game
考虑 Kruskal 的本质是贪心 。按边权从小到大扫描边，如果 u,v 不在同个连通块中，那么就合并 u,v 所在的连通块。
用最小表示法 记录每个点所在的连通块。状态数是 \text{Bell}(n) 个，带入 n=9 是 21147 个。
把所有边拆成两条排序后，对于在前面的那条，可以选择它是否存在；对于后面的那条，它必须存在。用 map<array<int, 9>, int> 记录下来转移即可。时间复杂度 O((n+\log\text{Bell}(n))m^2\text{Bell}(n)) 。
T2 排列 | CCPC 威海 2021 C Assign or Multiply
见过一遍的 trick 啊，场上怎么忘了/ll
求出原根 后，转化成模意义下的可达性背包问题。
考虑加入物品 v 的本质是用两个区间 [l,r] 去更新 [l+v,r+v] 。考虑用哈希 求出两个区间每一个不相同的位置。不同的位置有两种，分别是 0\to1 和 1\to0 。只有 1\to0 是有用的。
再考虑另一种建模，连边 x\to x+v ，这样会得到若干个置换环 。置换环上 0\to1 和 1\to0 的边数相等，所以上面的更新中，每找到两个不同的位置，就会有一次实际的更新。而更新不超过 p-2 次。
树状数组可以动态维护哈希值，查询时分治 即可。时间复杂度 O((n+p)\log^2p) 。
T3 排列 | PA 2022 Runda 5 Chodzenie po linie
考虑判断连通性 ，如果 \max_{1\le i\le r}a_i=r ，那么 [1,r] 和 (r,n] 就不连通。这样划若干条分割线后会得到若干个连通块，对于每个连通块分别考虑。
将贡献 \sum_i\text{dis}(p,i) 拆成 \sum_{i,j}[\text{dis}(p,i)\ge j] 。考虑从点 p 出发 j-1 步不能到达的点的形态，它们会构成两个左下 / 右上的区域。
两个区域是独立 的，以左下角的为例，设这个矩形的右上角端点为 (x,p_y) 。考虑递推 j\gets j+1 时的变化，x 会变为矩形区域外的点的横坐标 \min ，p_y 会变为矩形区域外的点的纵坐标 \min ，容易发现这两个值分别只跟 x,y 有关，写出来就是 (\min_{p_u\ge p_y}u,\min_{v\ge x}p_v) 。称这个过程为跳，最后会跳到 (1,1) 。
连边后可以得到一棵树，可以证明这棵树的点数是 O(n\sqrt n) 。
对于每个 (x,p_x) ，取其右下角纵坐标最小 的 \sqrt n 个点，称这些点是好的。
对于跳到的坏点 (x,p_y) ，由于 p_y 已经取了上一步中 x' 右下角纵坐标最小的 \sqrt n 个点，但这个点是坏的，说明在 (x',x) 中存在至少 \sqrt n 个点被跳过了。而这样的跳跃至多发生 \sqrt n 次。
说明了从 (x,p_x) 出发跳到的坏点个数不超过 \sqrt n 个，所以总点数为 O(n\sqrt n) 。
考虑如果能建出这棵树，可以直接继承其父亲的答案，再加上自己的贡献。自己的贡献就是左下角的点的个数，有 n 次修改和 O(n\sqrt n) 次查询。可以用 O(\sqrt n)/O(1) 的分块平衡至时间复杂度 O(n\sqrt n) 。
建树可以用哈希表，但是模拟赛搬题人卡了这种做法，强制我们学习另一种。考虑给每个 x 维护一个 vector，其中按照顺序记录所有 p_y 。前面说了，(x,p_y) 跳到的点的纵坐标是由 x 唯一决定的，且 x 越大，p_y 越大。只要倒着扫 x ，判断 x' 的 vector 的末尾是不是 p_y' ，不是就 push_back，这样就保证了 vector 中的元素单调递减 ，同时建出了树。
需要注意的细节是：加入 (x,p_x) 这个点时不一定单调；可能 x=x' 。
正着再扫一遍 x 统计贡献即可。
Day 2
T1 火力全开
令 b_i\gets b_i-1 ，这样问题转化成选择一个值域上的区间，使得区间内 \sum a 加上区间前 k 小的 c 的和最大。
建线段树，每个节点维护 \forall i\le k 时的答案 e_{p,i} 。考虑怎么合并，只考虑跨过中心的贡献的话，右边的 \sum a 就一定会被算上，转移 e_{p,i}=\min_{1\le j\le i}(e_{lc,j}+c_{rc,i-j})+\sum a_{rc} ，其中 c_{rc,i-j} 表示 rc 中前 i-j 小的代价。
注意到这是 (\min,+) 卷积，并且 c_{rc,*} 是凸函数 ，所以可以分治决策单调性 进行转移。
时间复杂度 O(n\log n\log k+qk\log^2k) 。
T2 异或症测试 3 | Petrozavodsk Winter 2023 Day 6 A The Best Problem of 2021
先用线性基判掉无界的情况。设 $f_i$ 表示 $n=i$ 时的答案，$g_{i,j}$ 表示元素值域在 $[1,2^i)$ 内，秩为 $j$ 的线性基的个数。转移：$g_{i,j}=g_{i-1,j-1}+2^jg_{i-1,j}$。
我们考虑把线性基消成标准的，即没**有一个元素包含其它元素的主元**。考虑第 $i$ 个元素，如果它是主元，那么只有一种方案；否则对于剩下的 $j$ 个主元，每个主元都可以选择是否包含它，方案数是 $2^j$。
计算 $f$ 时就是用全部方案减去线性基秩小于 $i$ 的方案：$f_i=2^{2^i-1}-\sum_{j<i}f_jg_{i,j}$。
有没有大神教教我 100 分啊/kel
### T3 树上邻邻域数点
#### $l=0
二分模板题。
l=1 考虑从下向上确定每个点的点权，如果是叶子，那么暂时先不确定。考虑某个非叶子节点 p ，如果它有孩子是叶子，就把这些孩子放到集合 S 中。如果 S 非空，并且点 p 的父亲的点权也没确定，那么也把点 p 的父亲加入到 S 中。
考虑对 S 进行整体二分 。先问出 (p,1,m-1) 。对于 S 中除了最后一个点（这些点一定都是叶子），询问 (u,2,m-1) ，把这个结果与前面那个询问比较一下，如果有差异，那么就说明 a_u<m 。确定了这些点后，就可以确定最后一个点的取值了。这样可以保证每个点都用了 \log V 次询问。
现在点 p 的所有孩子都已经确定了，如果点 p 还没确定，任取一个孩子 u ，询问 (u,1,m-1) 即可。
l=2 感觉不是正常人出的，也不是正常人能写的。
Day 3 | 计数 DP
A 省选联考 2025 Day 2 C 封印
听懂了部分，不准备写。
看了两种本质不同的做法的题解，感觉都超出我的水平了。
B 省选联考 2023 Day 2 C 染色数组
听懂了第一问的部分，不准备写。
C IOI 2020 Day 2 A 装饼干
做法比较神秘。
从低到高考虑每位的限制。记 y 的第 i 位为 y_i 。
对于第 0 位的限制就是 a_0\ge y_0 ；对于第 1 位，从第 0 位多出来的 a_0-y_0 个饼干每两个可以兑换成一个，整理一下变成：a_0+2a_1\ge y_0+2y_1 。归纳可以说明第 i 位的限制为 \sum_{j\le i}2^ja_j\ge x\sum_{j\le i}2^jy_j 。预处理 c_i 表示前 i 位对 \sum_{j\le i}2^jy_j 的限制。
发现从低往高并不容易。考虑从高位往低位 DP，设 f_{i,b} 表示已经填完了高于 i 位的数，对第 i 位的限制是 \sum_{j\le i}2^jy_j\le b 的情况下，填前 i 位的方案数。
考虑转移，b 实时对 c_i 取 \min ：
第 i 位填 0 ，相当于限制直接给了第 i-1 位，方案数为 f_{i-1,b} 。
第 i 位填 1 ，要求 b\ge 2^i ，方案数为 f_{i-1,b-2^i} 。
朴素实现复杂度没有任何保证。考虑按 i:0\to k 的顺序分别算出 f_{i,c_i} 。然后在计算某个 i 时，如果 b\ge c_i ，那么就可以直接返回 f_{i,c_i} 。来分析一下复杂度：当 b<2^i 时，只会进入一侧递归；当 b\ge2^i 时，进入 f_{i-1,b} 的递归就会直接结束掉。所以时间复杂度 O(k^2) 。
D 1603E A Perfect Problem
做过，回顾了下。
E PA 2021 Runda 1 Od deski do deski
自己做没做出来，太难了。
考虑判定过程，设 b_i 表示前 i 个数能否被消完，转移：b_i=\text{or}_{j<i}[b_{j-1}\land a_j=a_i] 。
我们实际上只关心，[1,i] 能否被消完和所有 b_{j-1}=\tt{true} 的 j 中 a_j 的种类数 ，设 DP 状态为 f_{i,j,0/1} ，容易转移。时间复杂度 O(n^2) 。
F AGC022E Median Replace
考虑如何判定，从前往后扫，有些基本观察：
根据这些观察，考虑维护栈，这个栈只有 7 个状态：空，0，1，01，10，100，11。转移是容易的。
G The 3rd UCup Stage 34 C Median Operations
？
H NOI 2023 Day 1 T2 桂花树
？
I AGC064D Red and Blue Chips
待完成。
J AGC069D Tree and Intervals
？
K 924F Minimal Subset Difference
？
L USACO 22 FEB Phone Numbers P
？
M 1679F Formalism for Formalism
？
N 1740F Conditional Mix
？
O AGC008F Black Radius
做过，回顾了下。
P 集训队互测 2022 Range Minimum Element
？
Q AGC056B Range Argmax
待完成。
R NOIP 2024 D 树的遍历
做过，回顾了下。
S AGC035F Two Histograms
待完成。
T UNR #7 Day 2 B 反重：求熵
好像听懂了 n\le7 ，不准备写。
U NOI 2021 Day 2 C 机器人游戏
？
V NOI 2023 Day 1 C 深搜
？
Day 4
T1 树 | 1958I Equal Trees
我的 meet in the middle 做法（鏖战 4.5h）。直接枚举每个点选还是不选，时间复杂度 O(n2^n) 。枚举 S\subseteq[2,m],T\subseteq[m+1,n] ，考虑能和 T 拼起来的 S 的形态。一个点 s 可以出现在 S 中，当且仅当 s 在两棵树中的祖先和 s 子树中出现的 T 集合中的点相同。
枚举 T ，根据上述条件可以得出集合 A ，使得所有 S\subseteq A ，S 和 T 均可以拼接。枚举 S ，做高维前缀和，再枚举 T ，时间复杂度 O(n2^{\frac n2}) 。
最大独立集的做法。考虑保留一个最大的点集。点集 B 合法当且仅当 \forall i,j\in B ，i,j 在两棵树上的祖先 - 后代关系一样。构造图 G ，如果 i,j 在两棵树上的祖先关系不一样，那么连边 i-j 。
问题被转化成了求最大独立集 。考虑记忆化搜索做法，DFS(i, B) 表示前 i 个点已经选择，它们的领域的并集为 B 的最大独立集大小。考虑分析这样的复杂度：
于是直接暴搜的时间复杂度就是 O(n2^{\frac n2}) 。
T2 序列 | ARC066F Contest with Drinks Hard
考虑单组 O(n) 的做法。设 f_i 表示考虑了前 i 个数，强制第 i 个没选的方案数。
转移：f_i=\max_{j<i}f_j+\frac c2(i-j)(i-j-1) 。斜率优化 即可。
再对后缀做一遍得到 g_i 。考虑修改第 i 个点时，如果不选第 i 个点，那么贡献为 f_i+g_i 。否则考虑 i 所在的段为 (l,r) ，那么贡献为 f_l+g_r+\frac c2(r-l)(r-l-1) 。
把式子整理成 a_l+b_r-clr 的形式。考虑分治 ，分治到区间 [L,R] 时考虑跨过 m 的贡献，只要维护 [L,m] 的凸包，查询 (m,R] 做 chkmax；对另一边再作一遍即可。时间复杂度 O(n\log n) 。
T3 栈 | 737F Dirty plates
似懂非懂/ll，有没有大神教教我啊/kel
Day 5
T1 图上的游戏
怎么被我秒了/tx
实际上求和后 $c_i\neq2$ 都没有贡献（因为 $u\to v$ 的贡献次数和 $v\to u$ 的贡献次数相同，并且贡献相反），只要考虑 $c_i=2$ 的点的贡献和即可。
考虑每个 $c_i=2$ 的点，记 $v_i=\text{out}_i-\text{in}_i$。每个点取 $0$ 的贡献就是 $c_i$，取 $1$ 的贡献就是 $0$。按照 $|v_i|$ 排序后，A 肯定取奇数排名的 $\max(v_i,0)$，B 肯定取偶数排名的 $\min(v_i,0)$。
直接计数 DP，设 $f/g_{i,x,y}$ 表示取了 $i$ 个点，这些点入度和为 $x$，出度和为 $y$ 的方案数 / 权值和。把可能的 $(m+1)^2$ 个出度入度二元组按照差排序。
转移时枚举 $i,x,y$ 和这个二元组选了几次，要乘上一些多重组合数的贡献，分配 $c_i=2$ 的点的编号，入度和出度对应的边的编号。输出时枚举 $x,y$，剩下的 $m-x/m-y$ 的入度和出度还要分配给 $c_i=0/1$ 的点。
### T2 修理 | [UOI 2024 Zeroing the segment](https://www.luogu.com.cn/problem/P12559)
显然至少要操作区间中的 $2^{\max\text{highbit}}$ 次，于是把区间中的数按照 $\text{highbit}$ 分类。令 $k=\text{highbit}$，设操作一进行了 $2^k\le x<2^{k+1}$ 次，那么除了 $r-l+1+k$ 次之外，还要进行 $\sum[a_i>x]$ 次操作。也就是要最大化 $\sum[a_i\le x]-(x-2^k)$。
当这个式子 $>0$ 时，可以看作把 $a_i$ 和 $\le a_i$ 的数匹配，完美匹配后，失配的数的数量就是式子的值。因为是完美匹配，考虑 **Hall 定理**，最大匹配数量为 $n-\max _S\{|S|-|N(S)|\}$。
我们可以构造一个二分图，左部点集为 $\set{a_i}$，右部点集为 $1,\dots,n$，边集为 $\set{(a_i,j)\mid a_i\ge j}$，那么考虑 Hall 定理的时候，我们只需要考虑所有 $S=\set{a_i\mid a_i\le x}$，因为这个时候限制最严。那么 $r-l+1-\max(\set{a_i\mid a_i\le x}-x)$ 就是二分图的匹配数。
考虑扫描线右端点，查询时其实应该从右向左加入 $a_i$。于是我们强制加入右端点。如果此时没法在右部点找到匹配，那就要强制删去一个下标尽可能小的左部点。线段树维护 Hall 式子对于 $1\le x\le n$ 的值，找到横坐标最小，删去后可以使值均 $\ge0$ 的位置，并把它的匹配删去。用另 $\log V$ 棵**主席树**维护右部点的匹配。时间复杂度 $O(n\log V)$。
### T3 人员调度 2
传奇 $k=300$，$O(k^4)$ Floyd 过 5s！
待完成。
## Day 6 图论
### A [PA 2025 Runda 1 Teleport](https://www.luogu.com.cn/problem/P11915)
自己做没做出来，太难了。
### B [1656I Neighbour Ordering](https://codeforces.com/contest/1656/problem/I)
听懂了，但是我不会广义串并联图找哈密顿回路啊！
### C [Moscow Pre-Finals Workshop 2020 Day 5 M Travel Dream](https://qoj.ac/contest/1302/problem/6807)
待完成。
### D [Xmas Contest 2022 H Happy Game](https://atcoder.jp/contests/xmascon22/tasks/xmascon22_h)
太神秘了，听不懂啊/ll
### E [Petrozavodsk Summer 2023 Day 4 C Many Many Cycles](https://qoj.ac/contest/1356/problem/7177)
$O(m^2)$ 的做法很厉害。没听懂优化。
### F [PA 2020 Runda 5 Trzy drogi](https://www.luogu.com.cn/problem/P9105)
臭名昭著的题目，怯战了。
### G [ARC122F Domination](https://atcoder.jp/contests/arc122/tasks/arc122_f)
做过，回顾了下。感觉还是很困难。
### H [CCPC Final 2022H Marriage II](https://qoj.ac/contest/1869/problem/9844)
我们二分图增广路真是太神秘了！但是我不会支配树啊/ll
### I [CF1284G Seollal](https://codeforces.com/contest/1284/problem/G)
~~拟阵是什么？~~
### J [Petrozavodsk Winter 2021 Day 4 I Color](https://qoj.ac/contest/532/problem/895)
待完成。
## Day 7
### 畅游广州！
## Day 8
### T1 序列变换
第一次没做出 T1/ll
记 $b_i=a_{i-2}+a_{i-1}+a_i$，可以转化成一个长度为 $n+2$ 的序列做如下操作：
+ 操作一：选择两个 $\bmod\ 3$ 意义下相同的数，前一个 +1 后一个 -1
+ 操作二：选择三个 $\bmod\ 3$ 意义下均不相同的数，要求后两个相邻，给它们三个都 +1
由于操作而会使 $\sum b$ 产生改变，所以操作二的次数是已知的，目标就是最小化操作二。
考虑倒序扫描序列，要求扫描到 $i$ 时，$(i,n+2]$ 均以操作为 $0$。
+ $b_i=0$，不操作
+ $b_i>0$，被迫进行操作一，记一下 $\bmod\ 3$ 意义下操作一还有多少个 +1 还没进行。
+ $b_i<0
T2 追忆
听到题目名字，看到数据随机后，就怯战了。话说我单向 BFS 45 分，双向 BFS 怎么只有 15 分啊！
点 k 可以到达 O(\sqrt k) 个点。
对于编号不超过 \sqrt k 的点，这些点共 \sqrt k 个。考虑从任意一个点走一步，点的编号期望除以二。那么从 k 开始，期望跳 \log_2\sqrt k 步后会到达编号 \le k 的点。
因为每个点连出去两条边，所以跳的过程可以看成一棵 \log_2\sqrt k 层的满二叉树，树上也是 O(\sqrt k) 个点。
考虑取阈值 B ，预处理出编号 \le B 的点两两之间的距离，这部分可以时间复杂度 O(B^{\frac 32}) 完成。
查询时暴力 BFS，到编号 \le B 的点就停止，这部分时间复杂度为 O(\frac{n^2}B) 。
取 B=n^{\frac45} ，可以平衡到 O(B^{\frac65}) 。但是这样需要离线。取 B=n^{\frac23} ，可以平衡到 O(n^{\frac43}) 。这样可以开的下 B^2 的 short 用来预处理，访问比较连续，所以差不多快。手写 queue 卡卡常就通过了。
T3 小方的疑惑
先考虑 O(n^3) 做法。设 f_{u,i} 表示 u 子树中，从父亲处来了 i 的点权，子树内部分配点权的方案数。显然 f_u 是关于 i 的不超过 \text{size}_u 次多项式。维护这个多项式，合并时需要平移 a_u 个单位，可以用 a_u\sim a_u+\text{size}_u 这些点值代入两边卷积后，再插回来即可。还要做一遍前缀和。
注意到实际上有两种操作：前缀和 和平移 。关于平移，对每个多项式 F_u 维护平移标记 b_u ，表示还要复合上 x+b_u 。做 j 次前缀和可以视为跟多项式 \frac1{(1-x)^j}=\sum_j\binom{j+i-1}{i-1}x^i 卷积。因此我们转而维护这个多项式：F_u=\sum_ic_i\binom{x+b_u+i}i 。
考虑如何合并 F_u,F_v(\deg F_u\ge\deg F_v) 。在原先的 DP 中是直接卷积，但在这里正确的方式应该是代入点值，对点值卷积。不妨先把 F_v 的复合标记下传了。注意到：
\binom{x+b_u+i}i=\sum_{j=0}^i\binom{x+j}j\binom{b_u-1+i-j}{i-j}
用组合意义很好理解。所以复合标记可以 O(\deg^2F_v) 时间复杂度下传。
随后 F_v=\sum_ic_i\binom{x+i}i 。考虑把 F_v 写成关于 z 的生成函数 ，即：
\begin{aligned}
G_v&=\sum_jF_v(j)z^j\\
&=\sum_j\sum_ic_i\binom{j+i}iz^j\\
&=\sum_i\frac{c_i}{(1-z)^{i+1}}
\end{aligned}
于是我们可以枚举 i ，把 G_u 作 i+1 次前缀和，然后乘以 c_i 贡献到答案多项式。
考虑如何给 G_u 作前缀和，记前缀和后的结果为 G_u' 。
\begin{aligned}
G_u'(k)&=\sum_{j\le k}\sum_ic_i\binom{j+b_u+i}i\\
&=\sum_ic_i\sum_{j\le k}\binom{j+b_u+i}i\\
&=\sum_ic_i\left(\sum_{j\le b_u+k}\binom ji-\sum_{j<b_u}\binom ji\right)\\
&=\sum_ic_i\left(\binom{k+b_u+i+1}{i+1}-\binom{b_u+i}{i+1}\right)
\end{aligned}
对于和式中的前者，可以看出它相当于从 [z^k]G_u 平移到了 [z^{k+1}]G_u' ；对于后者，可以视为是常数项，也就是说 [z^0]G_u'=-\sum_ic_i\binom{b_u+i}{i+1} 。这样平移一次的时间复杂度是 O(\deg_u) 。
我们一共要平移 \deg F_v 次，总时间复杂度 O(\deg F_u\deg F_v) 。只要保证 \deg F_u\ge\deg F_v ，就可以树形背包分析到时间复杂度 O(n^2) 。
注意：其实我们要在每次合并完后对点值做一边前缀和，这可以视作点 u 有个初始多项式 F_u=1 ，这样与其它子树合并后效果就相当于前缀和了。
Day 9
T1 平衡树
将不含有关键边的极大连通块缩起来，会得到一棵只有关键边的树。又注意到，如果一条关键边的两侧都有别的关键边，那么它一定不会贡献到答案。再把这部分缩掉，可以得到一个菊花 。
记菊花的叶子的连通块权值和为 v ，把 (\text{sum}-v)-v 放到 set 中，相当要执行 [l,r] 次操作，将最大值 -1，其余值 +1，使得 |v| 最小。
考虑先模拟前 l 次操作，可以二分上界或者取最大值不停与次大值合并。后面还可以进行至多 r-l
次操作。分 \max|v| 在正整数最大值和负数的相反数中讨论。如果是后者，还要再写一个二分。
时间复杂度 O(n\log n) 。
T2 上升树
传奇选手对值域 [1,n] 的数组离散化，而且离散化还写错了，Pre test 喜提 55 分！
考虑如何求出一棵树的 LIS，记 f/g_p 表示包含点 p 的 p 子树内的 LIS / LDS。可以用线段树 + 启发式合并求出每个子树内的 LIS。
顺便记录 LIS 的端点，就能求出全局最长 LIS 的两端 u,v 。显然要删除链 上的点。我们要对每个链上的点做换根，这很简单，只要把 u,v 当作树根分别做一遍即可。
时间复杂度 O(n\log^2n) 。
T3 并行程序 | PA 2020 Runda 5 Programowanie współbieżne
看懂了前四个子任务的题解。后面只能说：非常好 O(1) ，使我大脑旋转。
有没有大神教教我啊/kel
Day 10 数学
A 梦现时刻
配凑式 Ad-Hoc 浓度太高。
待完成。
B 1644F Basis
?
C XXI Open Cup Stage 14 H Harsh Comments
做过，当时还是 O(n^3) 的 min-max 容斥做法，回顾了下。
D AGC034F RNG and XOR
待完成。
E 集训队互测 2024 欧伊昔
懂了 mex 的子任务，没太懂后面的随机化。
F Xmas Contest 2020 D Determinant
?
G 集训队互测 2021 愚蠢的在线法官
?
H JSC 2023 Final H Adjacent Binomial Coefficients
?
I World Tour Final 2019E e
?
Day 11
T1 这是第一题
大战网格的一天！
就是要求 SG 值，SG 值域为 [0,3] ，对每行前后缀扫，维护前缀 / 后缀的函数即可。时间复杂度 O(n^2/n^2\log n) 。
T2 这是第二题
赛场上的错误思路：注意到操作五很麻烦。对于前四种操作，都可以行列拆开。尝试对操作五也进行行列拆开，构造操作 1',2',3',4' 使得 51=1'5,52=2'5,53=3'5,54=4'5 ，而 55=13 ，这样就能把操作五换到一起，然后消掉。
这样再把行列按照 \bmod\ 4 分类后，确实可以构造出来。但是问题是后面没法进行置换的快速复合。
把网格无线翻折，铺满整个平面，但是染色仍然是奇偶染色。这样操作 2,4 就是对所有网格都操作，不用特殊考虑边界。1,3,5 操作都是可以正常进行的。并且由于网格是无限的，只要取出 4\times4 的方格作为代表元，模拟这些数。其它数都可以由这 16 个数推出。
T3 这是第三题
有没有大神教教我啊/kel
Day 12
T1 硬币
做了好久啊，只会个不知道正确性的做法。
考虑什么时候可以一次操作完成。排序后，第 i 元素要 \ge i-1 。于是不停进行如下操作：
T2 厵神
log 比根号慢/fn
记题目中的两个点分别是 (sx,sy),(tx,ty) ，两个时刻分别是 s,t ，不妨认为 s\le t ，这种情况显然更强。两维都有限制很难处理，想办法把限制拆开。对每条路径，我们可以枚举走了 i 步是横着走的，其它步是竖着走的，这样两维就独立了。
记 a_{i,x,x'} 表示只考虑在一行中横着走，走了 i 步从 x 走到 x' 的方案数，b_{i,y,y'} 表示只考虑在一列中竖着走，走了 i 步从 y 走到 y' 的方案数。答案可以写成：
\sum_{x,y}\sum_i\binom tia_{i,x,tx}b_{t-i,y,ty}-\left(\sum_i\binom{t-s}ia_{i,sx,tx}b_{t-s-i,sy,ty}\right)\sum_{x,y}\sum_i\binom sia_{i,x,sx}b_{s-i,y,sy}
考虑求出 c_i=\sum_yb_{i,y,ty} ，也就是在一个二维平面上从 (0,ty) 开始，不能触碰直线 y=0 和 y=m+1 。每次向右上方 / 右下方走一个单位直到 x=i 为止。要对 1\le i\le t 都求出 c_i 。
设 f/g_i 表示第一次触碰直线是走了 i 步，触碰了直线 y=m+1/0 的方案数。记 \text{calc}(x,\Delta y) 表示走了 x 步，横坐标移动量为 \Delta y 的方案数。有递推式：
\begin{cases}
f_i=\text{calc}(i,n+1-y)-\sum_{j<i}(f_j\text{calc}(i-j,0)+g_j\text{calc}(i-j,n+1))\\
g_i=\text{calc}(i,y)-\sum_{j<i}(g_j\text{calc}(i-j,0)+f_j\text{calc}(i-j,n+1))
\end{cases}
显然可以分治 NT T 直接处理，但是常数太大了。考虑写成生成函数：
E_f=\sum_i\text{calc}(i,n+1-y)\\
E_g=\sum_i\text{calc}(i,y)\\
H_0=\sum_i\text{calc}(i,0)\\
H_1=\sum_i\text{calc}(i,n+1)\\
\begin{cases}
E_f-H_0F-H_1G=0\\
E_g-H_0G-H_1F=0
\end{cases}
可以解出：
\left(H_0+\frac{H_1^2}{H_0}\right)F=E_f-\frac{E_gH_1}{H_0}\\
\left(H_0+\frac{H_1^2}{H_0}\right)G=E_g-\frac{E_fH_1}{H_0}
多项式求逆 即可。那么就容易求出 c_i=2c_{i-1}-f_i-g_i 。
在考虑求出 b_{i,sy,ty} ，也就是把终点改到了中间，但是这里没有在 b_j 和 b_i 之间转移，所以可以直接多项式乘法解决。
时间复杂度 O(n\log n) ，需要乘法的次数较多，常数较大。
官方做法是根号分治 。
平衡后时间复杂度 O(n\sqrt n) 。
T3 区间压缩
区间的长度可以这样表示：
把区间转化成括号，令下标相同的左括号在右括号前面。区间的宽度就是 () 子串的数量。
可以构造性证明，如果原区间包含第 a 个 ~ 第 b 个子串，那么 [s_i,t_i]=[a,b] 。容易发现不能更小。
问题转化为求出所有子序列中 () 个数的总和。由于是合法括号序列，所以除了空串外，可以转化成 )( 个数加一。
这样转化的好处时，询问的是一个区间，截取后不完整的区间可能是前缀左括号被删去或者后缀右括号删去，不会影响贡献的计算。转成概率计算，扫描线 (，在线段树上维护所有 ) 和当前 ( 构成 )( 的概率和历史和。可以好用线段树 +矩阵乘法 维护。时间复杂度 O((n+q)\log n) 。
Day 13 树上问题
T1 ICPC 济南 2023 B Graph Partitioning 2
秒了 O(n\sqrt k) ，O(n) 挺厉害的。待完成。
T2 Petrozavodsk Summer Camp 2019 Day 2 J Jiry Matchings
?
T3 150E Freezing with Style
做过 O(n\log^2n) 单调序列启发式合并做法，回顾了下。
T4 浙江省选 2019 Day 1 B 语言
做过，回顾了下。
T5 Ynoi 2008 rdCcot
?
T6 Ynoi 2011 成都七中
?
T7 Ynoi 2008 rplexq
?
T8 2022 集训队互测 树
?
T9 The 2nd Ucup Stage 24
?
总结
四道不会的模拟赛题：
有没有大神教教我啊/kel
感觉来广州状态不好。前四场每场只会 T1，但发现 T2 都不难。后面四场开始狂冲 T2，产生了若干次差点时间导致 100 变 0 的惨状。在最后一场比赛的最后一分钟，终于首次通过 T2。
模拟赛题目质量还是可以的，但是部分分设计经常有问题，这样使得会做和不会做差异特别大，可能我不能要求太多。还是没学会攻击交互库，这很遗憾了。 讲课难度非常不均衡，可能有些感觉太难了，我就直接放弃了。让我思考，对于快要打 NOI 的选手，讲课到底有没有用。
这个活动各个方面，办的都还是挺好的。特别是茶歇室！从来没见过这么好的设计。终于久违的踢上了球，虽然实力下降实在太多。
这个月，打了特别多特别多的模拟赛。终究还是迷失了。
最后获得铜牌 rk35，虽然拿银牌其实比较容易，但是离金牌还有些距离。加油吧！