最后一年了，以后的做题记录大概会是这样的 Solution Set 形式，大概每周末会更一次。也许能起到防止开摆的作用。
做题速度过慢导致的做题广度不够，对难题的恐惧导致的训练强度过低……从未被提醒过，自己栽了跟头才意识到问题。
这周文化课，晚上的时间拿来做了下 AGC，但是怎么前面的题都不会做/fn
1 AGC064D Red and Blue Chips
可以尝试这么转化：建立边，然后颜色是 DFS 序。但是没用。
关键在于如何判断一个序列是否合法，也就是已知结果序列。那么可以得到最终的状态：\(n\) 号柱子上是结果序列，其余是空的。于是可以考虑倒着还原序列。在原序列上做，假如遇到了一个 B，那么就需要把之前的一个柱子劈开放在当前柱子上；假如遇到了一个 R，那么就需要选一个柱子上的 R 删掉。那么我们需要让可以使用的 R 尽可能多，也就是说我们事实上可以贪心地劈柱子，每次选择最大的段劈开。
那么原问题就转化成了一个序列上的问题：对于一个序列 \(l\)，\(l_i\) 表示在结果序列中第 \(i\) 个 B 上面有几个连续的 R；对于序列 \(r\)，\(r_i\) 表示原序列中第 \(i\) 个 B 左侧有多少个 R。那么条件等价于：
- \(\sum l_i=n-m\)，\(m\) 是 B 的个数。
- \(s_i\geq \sum_{j\leq i}r_i\)，其中 \(s_i\) 是 \(l_i\) 的最大的 \(i\) 个数的和。
DP 是平凡的，可以轻易做到 \(\mathcal{O}(n^3)\)。
https://atcoder.jp/contests/agc064/submissions/47786407
2 AGC064C Erase and Divide Game
比较暴力的一个题。
考虑暴力的做法：建立低位 Trie，然后就是有向图博弈问题。
然后其实是没什么性质的。考虑按照层数暴力往上 DP。定义 Trie 上一个节点的权值为 \(\sum 2^ie_i\)，其中 \(e_i\) 是从上往下第 \(i\) 条边的权值。那么 \(x\) 的值由下一层 \(x\) 和 \(x+2^k\) 的值决定。那么把序列劈成两半然后合并起来。但是值比较多，所以只能维护若干个区间，表示该层值在这个区间内的所有数的答案是一样的。因为每层只会增加 \(\mathcal{O}(n)\) 个区间所以复杂度为 \(\mathcal{O}(n\log^2 V)\)。
https://atcoder.jp/contests/agc064/submissions/47805345
3 AGC063C Add Mod Operations
为啥我就做不来构造呢。
考虑 \(n=1\) 怎么做，可以设置一个极大值 \(P\)，操作 \(((b_1-a_1+P)\bmod P,P)\) 即可。
考虑 \(n>1\)，发现如果每次操作最大值，就可以把最大值置为 \(0\)，然后其它数加上一个值 \(x\)，即操作 \((x,x+\max a_i)\)。
这个操作非常强力。马上可以想到一个思路：从大到小依次确定 \(x\)，然后依次操作。设第 \(i\) 次操作为 \(x_i\)，那么操作 \(n-1\) 次的结果是：
不妨设最后一次操作 \(b_2\)，那么列一下方程即可得到：
你注意到 \(x_i\) 可能会是负数，所以可以仿照上面给 \(x_i\) 加一个极大值 \(P\)，最后操作 \(x_n\) 的时候取模数为 \(P\) 即可。
https://atcoder.jp/contests/agc063/submissions/47824461
4 AGC062B Split and Insert
感觉好抽象。
考虑倒着做，每次选择 \(k\) 个数放到最后面。那么最后一次操作一定是把值域在 \([x+1,n]\) 中的所有数选出来提到后面去，并且保证值域在 \([1,x]\) 和值域在 \([x+1,n]\) 中的所有数位置都是递增的。那么在前面的操作中我们需要把 \([1,x]\) 排序和 \([x+1,n]\) 排序，而两边是独立的，所以可以分开做。于是设 \(f_{i,l,r}\) 表示从 \(k\to i\) 的操作中把 \([l,r]\) 排序的代价，转移式子是：
复杂度是四次方。
https://atcoder.jp/contests/agc062/submissions/47828446
5 AGC062C Mex of Subset Sum
终于做出来了，虽然不会证复杂度/ll
下面认为 \(a_i\) 是不降的，且 \(pre_i\) 为 \(i\) 的前缀和。处理 \(k\) 有点棘手，但是求出最小的数是容易的。
考虑怎么判断一个数不能被表示，从 \(1\sim n\) 依次遍历每个数，考虑 DP 的过程：\(f_{i,u}=f_{i-1,u}\lor f_{i-1,u-a_i}\)，那么 \(u-a_i\) 显然不能被前缀 \(i-1\) 的数表示。假设 \(S_i\) 为前缀 \(i\) 不能表示的 \([1,pre_i]\) 区间内的数，那么 \(u-a_i\in S_i\)。所以可以尝试从小到大 BFS 不能被找到的数，如果检查 \(u\) 的过程中，\(u\in S_i\)，那么就把 \(u+a_i\) 加入优先队列。如果 \(u\in S_n\)，说明不能被表示，输出答案。
看起来不太靠谱。事实上有靠谱一点的做法。考虑从 \(S_i\) 推到 \(S_{i+1}\)，并且忽略掉 \(S_{i+1}\) 中无用的数。分类讨论：
- \(a_i>pre_{i-1}\)，其中 \(pre_{i-1}\) 为 \(i-1\) 的前缀和。那么 \(|S_{i-1} \cup((pre_{i-1},a_i)\cap \mathbb{Z})|\leq k\)，因为如果大于 \(k\) 那么把这些数输出就结束了。否则对于 \(S_i\) 中在 \([a_i,pre_i]\) 之间的数 \(x\)，需要满足 \(x-a_i\in S_{i-1}\)，所以 \(|S_i|\leq |S_{i-1}|+k\)。
- \(a_i\leq pre_{i-1}\)，那么 \(u\in S_i\land u<a_i\) 的数如果不会超过 \(k\) 个，否则直接结束。剩下的数需要至少满足 \(i-a_i\in S_{i-1}\)，这些数不会超过 \(|S_{i-1}|\) 个。
所以我们证明了如果在恰当的时候结束，\(|S_i|\leq ik\)。
其实要推这个的 motivation 很简单，就是观察到 \(k\) 很小，考虑分类讨论来约束 \(|S|\)。
https://atcoder.jp/contests/agc062/submissions/47867318
6 AGC061C First Come First Serve
考虑怎么判断一个排列是否合法：从小到大选，能选 A 就选 A。
直接判断不好判断，但是注意到选择方案和排列构成双射，不妨直接计数选择方案。一个选择方案合法当且仅当如果一个数选了 B，那么 \([A_i,B_i]\) 之间必须选了数。那么可以 DP：设 \(f_i\) 表示 \(i\) 为一个 A 连续段开头的方案数，枚举中间的一个 B 段进行转移。当然也可以直接容斥一下，比上面那个憨憨 DP 不知道好写到哪去了。
https://atcoder.jp/contests/agc061/submissions/47878221
7 AGC063D Many CRT
原题式子：
两边同时乘 \(d\)（保证 \(\gcd(c,d)=1\)）然后取模：
（不是很懂这步的 motivation，可以看做是同余式变形的一种技巧？）
这个同余方程的合并方式是显然的：
其中 \(M=\text{lcm}_{i=0}^{n-1}(c+dk)\)。
所以需要求出最小的 \(y\) 满足 \(v=My+(ad-bc)\bmod M\geq 0\) 且 \(v\bmod d=0\)。
注意到问题只和 \(M\bmod d\) 有关，所以考虑求出 \(M\bmod d\) 和 \(M\bmod 998244353\)，可以通过分解质因数的方式求解。
问题在于质因数可能很大，但是 \(\gcd(c+di,c+dj)\leq 10^6\)，所以可以把小于 \(10^6\) 的部分分解出来，剩下的单独乘。
枚举 \(p\)，找到最小的 \(i\) 使得 \((c+di)\bmod p=0\)，然后依次遍历 \(j=i+kp\)，不断除去 \(p\)。这部分复杂度是 \(\mathcal{O}(n\log\log n)\)。剩下的数一定是 \(1\) 或者单个素数，单独乘上即可。
回到原题，暴力枚举 \(y\) 即可。注意到我们不一定能求出 \((ad-bc)\bmod M\) 的精确值，这使得 \(v\geq 0\) 的限制不好处理，那么在 \(M\) 比较大的时候直接取 \(ad-bc\) 的值然后忽略 \(y=0\) 即可。
https://atcoder.jp/contests/agc063/submissions/47963804
8 AGC063E Child to Parent
实在有些神秘。
设 \(f_{u,i}\) 表示 \(u\) 往上传 \(i\) 的方案数，转移分为：
- \(g_{u,a_u+rs}=\sum\limits_{\sum x_i=s} f_{\text{son}_i,x_i}\)。
- \(f_{u,s}=\sum_{s'\geq s}g_{u,s}\)。
第二维状态比较大，考虑把它塞进式子里面。注意到如果能够求出所有方案中 \(a_u+rs\) 的和，就可以求出方案数。顺理成章地认为，如果想要维护 \(i^k\) 的和，就必须维护出儿子的 \(i^{k+1}\) 的和。那么设 \(f_{u,i}\) 表示所有方案中 \(u\) 子树向上传的数的 \(i\) 次方和，有：
后面是自然数等幂和，它可以写成 \(k+1\) 次多项式的形式，这印证了我们上面的想法。用伯努利数算一下这个 \(k+1\) 次多项式每项的系数就可以封闭转移。