加粗斜体表示思考时被卡了的部分。
AT
AGC010 E
考虑两个不互质的数，被先手确定顺序后就无法改变了。
考虑拓扑序和这个性质是类似的，如果存在 \(u\to v\)，则 \(u\) 的拓扑序一定先于 \(v\)。
于是问题变为，对于两个点 \((u,v)u\neq v\)，若 \(\gcd(a_u,a_v)\neq 1\)，则 \((u,v)\) 有边。
先手需要定向 \((u,v)\)，使得后手获得最大的拓扑序最小。
考虑贪心，对于每个连通块都要去到最优。对于一个连通块，我们考虑：钦定最小的那个点为根，开始 dfs：
如果当前 dfs 到 \(u\)，那么找到所有邻居 \(N\)，按照从小到大的顺序访问 \(i\in N\)：
- 如果 \(i\) 已访问，则跳过；
- 连边 \((u,i)\)，递归进 \(i\)。
ARC 104
A,B 略过。
C
考虑一个区间 \([l,r]\) 里有 \(d=(r-l+1)/2\) 个人，每个人的上下电梯关系一定是 \((l,l+d)\)。
然后 \(w(l,r)\) 表示 \([l,r]\) 作为一个区间是否可能。这是好算的。
转移就是 \(f(i)w(i+1,j)\to f(j)\)。
复杂度 \(O(n^3)\)。存在平方做法。
D
考虑平均数要记录元素个数，不太好。
枚举平均数为 \(v\)，那么每个数变成了 \(v+d\)，问题变成选择一些 \(d\) 使得 \(\sum d_i=0\)。
考虑 \(f(i,j)\) 表示选择前 \(i\) 种 \(d\)，\(\sum d_k=j\) 的方案数。
状态数是 \(O(n^3k)\) 的，转移使用前缀和优化是 \(O(1)\) 的。
注意到更换平均数的时候不需要重新计算，只要把 \(f(k-1),f(n-k)\) 拼起来就好了。
E
\(n\) 非常小，考虑一些暴力。
首先 \(n^n\) 枚举数的大小关系，然后可以用 \(O(n^3)\) 的 dp 算出方案数。
复杂度：跑不满的 \(O(n^{n+3})\)。
ARC 105
A,B,C 略过。
PS：我认为 DE 一个难度。。
D
考虑对 \(n\) 奇偶分类：
- \(n\) 为奇数，则后手想要让 \(SG\neq 0\)，后手只要每次选择袋子中最多的那堆石子，放到先手第一轮放的那个盘子里，那么最后这个盘子石子的个数一定严格大于总石子的一半。因为异或不超过加法，所以另外的异或一定小于该值。故 \(SG\neq 0\)。故后手必胜。
- \(n\) 为偶数，则先手想要让 \(SG\neq 0\)，最优方案仍然是每次选择最多的。但是如果每种大小的石头出现偶数次，则后手可以复制先手的操作，使得 \(SG=0\)。
故先手胜利当且仅当 \(n\in \text{even}\) 且存在一种大小的石头不出现偶数次。
E
注意到最后情况一定是，存在两个连通块 \(1\in S,n\in T\)，同时 \(S,T\) 是完全图。
此时已经走了 \(\frac{n(n-1)}{2}-m-|S||T|\) 步。根据这个的奇偶性可以得到先后手谁胜利。
仍然是考虑奇偶分类。
-
\(n\) 为奇数，则 \(|S||T|\) 必为偶数，所以谁胜利只和 \(\frac{n(n-1)}{2}-m\) 有关。如果是奇数则先手，否则后手。
-
\(n\) 为偶数。考虑对 \(|S|,|T|\) 的奇偶分类讨论。这里假设 \(\frac{n(n-1)}{2}-m\) 是偶数。
-
\(|S|\in\text{even},|T|\in\text{even}\)
先手想要胜利，则要维持 \(|S|,|T|\) 的奇偶性不变。考虑先手可以把偶数并到 \(S,T\) 中，或者把两个奇数合并为偶数，后手如果把奇数并到 \(S,T\) 中，先手复制操作。故先手可以保持奇偶性不变，先手必胜。
-
\(|S|\in\text{even},|T|\in\text{odd}\)
考虑先手第一步可以转化为上一种情况，同时 \(\frac{n(n-1)}{2}-m'\) 变为奇数，故先手必胜。
-
\(|S|\in\text{odd},|T|\in\text{even}\) 同上，先手必胜。
-
\(|S|\in\text{odd},|T|\in\text{odd}\) 和第一种情况同理，后手必胜。
如果 \(\frac{n(n-1)}{2}-m\) 为奇数是同理的。
-
于是做完了。
F
不考虑联通，设 \(g_S\) 表示点集 \(S\) 构成二分图的方案数。枚举 \(T\) 为左部点，则 \(S-T\) 为右部点，可以计算出方案。
考虑联通，\(f_S=g_S-\sum\limits_{T\subsetneq S,\min T=\min S} f_Tg_{S\setminus T}\)
答案即为 \(f_U\)。
CF
CF 2127
E
考虑最优的填色情况，如果一个点还没有颜色，并且其子树中存在颜色，那么这个点的颜色一定是子树里已经有的颜色，否则一定不优。
然后考虑一个点什么时候会被算入代价，那一定是这个点同时在多种颜色的虚树上。同时我们注意到，把一个没有颜色的点填色，其颜色虚树是不变的，所以这个贪心是最优的。
F
首先考虑如何求出满足：
- \(\sum_{i=1}^n a_i=m\)
- \(a_i\in [0,x]\)
的 \(a\) 的方案数（设为 \(F(n,m,x)\)）。
考虑二项式反演，\(g(i)\) 表示钦定 \(i\) 个位置 \(>x\) 的方案数，\(f(i)\) 表示恰好 \(i\) 个 \(>x\)。
有 \(g(i)=\binom{n}{i}\binom{m-(x+1)i+n-1}{n-1}\)。
同时 \(g(i)=\sum_{j\geq i}\binom{j}{i}f(j)\)。
则 \(f(i)=\sum_{j\geq i}\binom{j}{i}(-1)^{j-i}g(j)\)。
故我们可以在 \(O(\frac{m}{x})\) 的时间内算出 \(F(n,m,x)\)。
然后考虑原题。首先原题可以转化为，\(f(a)=-a_1+a_n+\sum_{i<n,a_i=a_n}(a_i-a_{i+1})\)。
然后分别计数。
首先是 \(a_n\)，枚举 \(a_n\)，然后方案数是 \(F(n-1,m-a_n,a_n)\)。
然后是 \(-a_1\)，枚举 \(a_n\)，然后方案数是 \(F(n-1,m-a_n,a_n)\)。
考虑每个方案的和是 \((m-a_n)F(n-1,m-a_n,a_n)\)。
同时每个位置期望相同，所以 \(-a_1\) 所有情况下的和是 \(-\frac{m-a_n}{n-1}F(n-1,m-a_n,a_n)\)。
最后是 \(\sum_{i<n,a_i=a_n}(a_i-a_{i+1})\)，考虑拆贡献，对每个 \(i\) 计数。
因为 \(i\) 在哪里都是等价的，所以只要算出某个 \(i\)，然后乘以 \(n-2\) 即可。
考虑枚举 \(a_n\)，然后方案数 \(F(n-2,m-2a_n,a_n)\)，同理 \(a_{i+1}\) 大小是 \(\frac{m-2a_n}{n-2}F(n-2,m-2a_n,a_n)\)。
加起来就好了。
MX-BJ-A
Day 6
gcd
首先贪心，选择 gcd 相同时最短的段。可以看做是从起点不断跳出边到达终点右侧的步数。
注意到一个点的出边 \(O(\log n)\) 条，倍增跳 相同的边，复杂度 \(O(n\log^2 n\log\log n)\)。
irris
画画图，发现一个点经过 \(k\) 次左儿子有兄弟变换后的父亲和 dfn 序有关，所以把树离线下来，维护当前被点亮的点在 dfn 上的位置，线段树上二分即可。
shiro / CF1322F
先用带权并查集维护边的关系。
先二分答案。考虑判定。
考虑已知 \(\lim\) 的情况下，当前树的根节点 \(x\) 的取值范围。
这里假设 \(x\) 的父亲边满足父亲比儿子大。如果方向不同，取值区间是沿着中轴对称的。
注意到我们只需要维护 \(x\) 的最小值。
考虑转移：
- 如果儿子边和父亲边属于同一个并查集，那么直接做转移。
- 否则把不同并查集的儿子边内部做 \(\text{and}\)，然后转移是当前和对称的并。
然后考虑第二种情况可能会有两个区间。因为区间是对称的，所以只维护左侧，求完再对称到右侧，最后和第一种情况得到的那个区间求交即可。
然后考虑构造。
反着做，如果当前 \(x\) 的某个儿子 \(i\) 使用原来 dp 值得到的转移区间不包含 \(ans_x\)，说明 \(i\) 的 dp 值要对称一下。然后递归做下去。
Day 7
nine / AtCoder wtf19_b
先离散化，然后并查集维护连通块。
考虑枚举每一位填了集合 \(S\) 中的位置，那么贡献可以预处理出来为 \(w(S)\)。
把集合幂级数弄出来，是 \(F(x)=\sum_{S\subseteq U} w(S)x^S\)
然后可以子集卷积快速幂做到 \(O(2^nn^2\log)\)。
问题在于 \(w(S)\) 是多少。
考虑对于离散化后相邻的两个位置 \(l,r\) 之间的段，原来有 \(\dfrac{10^{r-l}-1}{9}\) 种选择，然后如果 \(v_l=v_r\)，则有 \(\dfrac{10^{r-l}+8}{9}\) 种选择。
所以 \(w(S)\) 就是 \(\prod_{(l,r)\in T}\dfrac{10^{r-l}+8}{10^{r-l}-1}\)。
其中 \(T\) 是满足 \((l,r)\) 相邻且 \(l\in S\land r\in S\) 的集合。
Day 8
sakura / Gym 103428C
歪解：使用 bitset + 二进制分组 + 打乱后取前（常数）个 暴力。
正解：考虑直接求出每次操作会让多少个位置变成 1。
放松限制，考虑求出每次循环移位 \(x\) 并且取或前，满足 \(i\) 和 \(i+x\) 不同的 \(i\)。这和变成 \(1\) 的位置个数同阶。
注意到可以使用哈希二分之类的求出每个位置。然后做完了。
tsuki / QOJ 4299
考虑如果一个点的度数是偶数 \(2d\)，那么存在一条欧拉回路。沿着回路定向，可以让出度入度都为 \(d\)。
那么考虑度数是 \(2d+1\) 的，意味着存在一种定向方式使得一个点的出度和入度之差不超过 \(1\)。
然后我们 \(2^n\) 枚举出度多还是入度多，然后拆点跑网络流。复杂度 \(O(2^nn^3)\)。
kaze / AtCoder ddcc2020_final_d
难评。
考虑基环树的直径怎么求。分为过环直径和树内直径。
树内直径好求，过环直径稍微麻烦一点，但是也不难求。
然后是删点后求直径。设删除点 \(i\) 属于树 \(T\)。
考虑树内直径的变化，使用一个换根 dp 求解。这里同时记录删除某个点后 \(T\) 的深度。
然后考虑过环直径，记录不经过 \(T\) 内的最长路径，以及从 \(root(T)\) 开始到达 \(T\) 外的最远位置。
把这几种拼在一起就好了。细节多。