Contest Round 1
木积
description
给你 \(n\) 个数 \(a_i\)，你需要求出可以选出的最大子集大小，使其中的数两两之间互质。
\(1 \le n, a_i \le 10^3\)。
solution
首先题目给这么小的数据范围不是当饭吃的，首先我们考虑 \(a_i \le 1000\) 有没有啥特殊的性质。
容易想到的一个做法是，对 \(1000\) 内的所有质数直接状压，然后对每个数都跑个 DP，这样子是对的，但是 \(1000\) 内的质数个数也绝对不少，会直接 out 掉。
然后我们考虑经典减少质因子个数的思路：某个数 \(x\) 的 \(>\sqrt x\) 的质因子最多只有一个！证也很好证，就是根据唯一分解定理，入如果有两个质因子肯定都在 \(x\) 的质因数分解序列里，但是两个相乘就爆 \(x\) 了，所以最多只有一个。
然后就很好做了，你考虑 \(\sqrt {1000}\) 也就是大概 \(35\) 内最多只有 \(11\) 个质数，这下你就可以状压了，但是如果 \(> sqrt(1000)\) 咋办呢？考虑这样的质数也不到 \(1000\) 个，在做 DP 的时候，我们可以从每个大于 \(35\) 的质数序列中选一个进行转移，他们说有点类似背包？
远游
description
你有一个大小为 \(3 \times n\) 的网格，你现在往里面随机放入 \(1 \times 1\) 障碍和 \(2 \times 2\) 的障碍，如果走到第 \(i\) 列，那么贡献就是 \(i^k\)，问可能的期望贡献。
\(1 \le n \le 10^18\)。
solution
首先看到这个题目你可以想到一个 DP 状态 \(f_{i, 0/1, 0/1, 0/1}\)，表示到了第 \(i\) 列的状态，然后考虑把后缀的信息求过来做一个前缀和，这样你就会 \(O(n)\) 咋做了。
但是我们发现这个 DP 式子是很经典可以用矩阵快速幂优化的，于是我们把它写成一个大小为 \(8^3\) 的一个矩阵，但是你注意到 \(T = 500\)，所以还是不能过。
题解给出的做法是优化状态，我选择暴力打出矩阵去掉稀疏行列最后优化到一个不明复杂度。
蒟蒻座蒟蒻星
description
就是给你一颗基环树，每次让你断掉两条边后求两颗树的树的直径的和。
\(1 \le n \le 10^5\)。
solution
考场时以为是树的中心就跳了qwq。
然后我们发现这么一个事情，就是我们将基环树的环找出来，然后断环成链，对于链上每个结点维护一颗线段树，表示这个点的子树中的树的直径端点，根据经典引理，树的直径是可以 \(O(1)\) 合并的，然后我们分类讨论一下：
- 如果两条边都是环上的：正好链被断成两个，我们直接线段树查询即可。
- 如果一条边是环上的，一条边是树上的：我们发线 DFS 序可以直接合并，找到其他子树直接合并即可，这里我的想法是直接三度化然后这样合并就是 \(O(1)\) 的了。