考试LIST [2021.04]
2021.04.01
$\texttt{Location:HNOI2021}$
得分：$\texttt{70/300,Rank1}$。
[04.01]-错误
$\texttt{T1}$ 的 $\text{long long}$ 开少了......如果空间不超，能全用 $\text{long long}$ 就用吧。
[04.01]-部分正解
$\texttt{T1}$
考虑两棵树 $(m_1,b_1),(m_2,b_2)$满足什么条件才能一起结果，也就是存在 $c_1,c_2$ 满足：
$$ m_1c_1+b_1=m_2c_2+b_2 $$
一看就知道是个方程的形式，那么移项变成：
$$ m_1c_1-m_2c_2=b_2-b_1 $$
根据裴蜀定理，这个方程有解当且仅当：
$$ \gcd(m_1,m_2)|(b_2-b_1) $$
同时可以证明，当一个集合中两两可以同时结果，那么整个集合都可以同时结果（取个类似 $\text{lcm}$ 的东西即可）。
那么令 $\text{dp}_i$ 为第 $i$ 棵树向左最远可以延伸到什么位置，使得 $\text{dp}_i$ 到 $i-1$ 中每一棵树都可以和 $i$ 一起结果。接着就只需要对 $\text{dp}_i$ 取一遍前缀 $\max$，就可以知道以 $i$ 为右端点的合法区间有多少了。
那么 $[l,r]$ 的答案为：
$$ \sum_{i=l}^r i-\max(l,\text{dp}_i)+1 $$
由于 $\text{dp}$ 已经取过前缀 $\max$，所以这个东西可以直接二分，询问变成 $\mathcal{O}(q\log n)$。
接着考虑如何快速求 $\text{dp}$。如果枚举 $i,j$，判断 $i,j$ 是否合法，显然是 $\mathcal{O}(n^2)$，但是观察满足条件的柿子：
$$ \gcd(m_i,m_j)|(b_i-b_j) $$
那就枚举 $\gcd(m_i,m_j)$ 好了，这东西不超过 $m$。显然对于 $\gcd(m_i,m_j)$ 的约数 $d$，都有：
$$ d|(b_i-b_j) $$
这等价于：
$$ b_i\equiv b_j\pmod{d} $$
那么可以直接把每个 $m_i$ 扔到所有其约数的 $\text{vector}$ 里，然后用上述方法开个桶来更新 $\text{dp}$。如果用桶，可能要用树状数组维护前缀/后缀 $\max$，因为要维护桶中不同余于某个数 $d$ 的所有节点的下标 $\max$，用来更新 $\text{dp}$。同样可以指针维护距离最近的，与当前点不同余的位置，这少一个 $\mathcal{O}(\log)$。
但是这个东西的复杂度是：
$$ \mathcal{O}(\sum d(m_i)) $$
可以卡得很满，完全跑不过 $10^6$。但是观察发现，根据中国剩余定理，我们只需要对质数 $p$ 的次幂 $p^k$ 来判断即可，因为这样的话任何数字都可以通过中国剩余定理来合并了。
于是变成 $\mathcal{O}(n\log m)$ 或者 $\mathcal{O}(n\log^2 m)$，可以通过。
$\texttt{T2}$
圆方树+虚树+换根 $\text{dp}$。
还没改，所以现在他咕了
$\texttt{T3}$
这题和[CTSC2006]歌唱王国很像，但是又有所不同。
考虑 $\text{PGF}$。设 $f_n,g_n$ 分别表示序列长 $n$ 的时候恰好结束、还未结束的概率，其 $\text{PGF}$ 为 $F(z),G(z)$。那么：
$$ F(z)+G(z)=zG(z)+1 $$
$$ E(\text{len})=F'(1)=G(1) $$
这和上面那题一模一样，不再赘述。
接着沿用上述那题的思路，考虑强制让游戏结束。令 $s$ 为需要匹配的串，设 $P_i$ 表示，已经填完 $1$ 到 $i-1$，接着再填完 $i$ 到 $m$ 的概率。那么：
若 $s_i$ 是前缀 $1-i$ 中第一次出现，那么 $P_i=P_{i+1}\times \dfrac{n-c+1}{n}$，其中 $c$ 表示 $s_1$ 到 $s_{i-1}$ 中出现的不同字符个数。也就是可以选择一个没选择过的字符填入。
若 $S_i$ 不是前缀 $1-i$ 中第一次出现，那么 $P_i=P_{i+1}\times \dfrac{1}{n}$，也就是你必须和第一次出现的地方的字符一样。
于是 $P_1$ 就是填好整个序列的概率。那么有柿子：
$$ G(z)\times P_1z^m=\sum_{i=1}^m v_iF(z)P_{i+1}z^{m-i} $$
其中 $v_i$ 表示 $s$ 长度为 $i$ 的前缀是否是一个同构意义下的 $\text{border}$。也就是左右都多算了提前结束的部分之后形成的等式。
又 $F(1)$ 必然为 $1$，那么：
$$ E(\text{len})=F'(1)=G(1)=\dfrac{\sum_{i=1}^m v_iP_{i+1}}{P_1} $$
再考虑求 $v_i$。在 $s_i$ 中，令 $\text{pre}_i$ 为 $s_i$ 这个字符在 $i$ 之前最近的出现位置。那么定义：$b_i=i-\text{pre}_i$，若 $s_i$ 是第一次出现，那么 $b_i$ 为 $0$。
显然两个字符串同构当且仅当他们的 $b$ 数组相同。
那么只需要对 $b$ 做 $\text{kmp}$ 即可。但是需要特殊判断一种情况：对于一个长度为 $l$ 的后缀，若其中有一个位置 $s_p$ 是在这个后缀中第一次出现，但是不是在整个串中第一次出现，我们认为 $b_p=0$，这样才能与前缀相等，特殊设置一下即可。
因此时间复杂度为 $\mathcal{O}(m)$，甚至和 $n$ 都没啥关系。
[04.01]-总结
$\texttt{T1}$
这个题的形式是十分经典的，转化为整除的形式是没有难度的。
而本题使用了一个已经十分常见的套路，也就是转化为枚举 $\gcd$ 以降低时间复杂度。首先考虑一下为什么暴力枚举那么慢，因为如果直接对原式进行判断，那么整个柿子和 $b,m$ 都有关系，限制太多了不好优化。
但是枚举 $\gcd$ 的约数之后就不一样了，只需要考虑 $b$ 在同余系下的性质即可，这就有了优化的余地。这同样显示了一种通过变换枚举内容来给枚举项以更紧的限制，从而降低复杂度。
接着优化到素数次幂，主要是因为素数具有太多太好的性质，他们在极大多数情况下独立性极强，就如莫比乌斯反演中将 $\text{d}(m)$ 转化为 $2^{\omega(m)}$ 一样是利用了素数性质与题目特点的关联。这一般来说可以把 $\text{d}(m)$ 或 $\sqrt{m}$ 转化为 $\log m$ 甚至 $\omega(m)$，优化及其明显。
$\texttt{T2}$
看到仙人掌，先建圆方树
咕咕咕
$\texttt{T3}$
本题中一个 $\text{trick}$ 是关于同构字符串的判定。由于同构判定中无法使用单个位置的具体值来进行判断，但是值之间的相对关系在同构关系中同样的不变的。也就是说，在同构问题中，考虑相对关系往往是一种方法。
同时本题使用了一种思想：在算重/多算的时候，不删去重复部分，而是通过类似的形式建立另一个柿子，使得两个柿子具有相同的意义（即使是多算的也都保持一致），然后使用方程等方式解决问题。
2021.04.03
$\texttt{Location:HNOI2021}$
得分：$\texttt{138/300,Rank3}$。
[04.03]-错误
$\texttt{T1}$ 忘记特判 $x=0$ 的情况，主要原因是没有拍。
[04.03]-部分正解
$\texttt{T1}$
从高位往低位建立 $\text{01trie}$，考虑 $x$ 的每一位，记录 $s_i$ 为 $i$ 子树中，最后这些位中 $\text{xor }\ge x$ 的组合有多少。
若 $x$ 当前位为 $0$，则当前节点的 $s$ 为：左子树中数字的合法方案 $\times$ 右子树中数字的合法方案，因为跨过当前节点的组合必然合法，他们这一位异或为 $1$ 而 $x$ 中这一位为 $0$。
若 $x$ 当前位为 $1$，则只能在左子树、右子树各选择一个。因为只有任意两个都跨过当前子树根才可能 $\ge x$。因此写另一个 $\text{DFS}$，组合计算一下子树内有哪些点对是可行的即可。
每个节点都只会被遍历 $1$ 次，复杂度 $\mathcal{O}(n\log v)$。
$\texttt{T2}$
容斥，变成：
$$ k^n\times(n-x)-\sum_{i=x}^{l-1} c_i $$
其中 $c_i$ 表示：$\max{L(a)}\le i$ 的染色方案数。实际上就是一开始多算了 $n-\max{L(a)}$，逐个减掉即可。
然后这个 $c_i$ 可以 $\mathcal{O}(n^2)$ 通过 $\text{dp}$ 求解，类似背包的方式，限制一下一个连续段的最大长度为 $i$ 即可。设 $\text{dp}_{i,n}$ 表示将长度为 $n$ 的序列染色，每段不超过 $i$ 的方案数，那么：
$$ \text{dp}_{i,n}=(k-1)\sum_{l=1}^{\min(i,n)}\text{dp}_{i,n-l} $$
最后还要乘一个 $\dfrac{k}{k-1}$，因为第一个段有 $k$ 个颜色可选。
这显然可以前缀和优化一下，那不妨直接先求出一下前缀和，设 $s_{i,n}=\sum_{j=1}^n \text{dp}_{i,j}$，那么：
$$ s_{i,n}=(k-1)(s_{i,n-1}-s_{i,n-i-1})+s_{i,n-1} $$
化化柿子变成：
$$ s_{i,n}=k\times s_{i,n-1}+(1-k)\times s_{i,n-i-1} $$
由于我们最后只需要对于不同 $i$，相同 $n$ 的 $\text{dp}_{i,n}$，因此考虑快速求解这个东西。由于转移方式实际上很单一，只有两项，所以考虑给他一个组合意义。
观察发现，可以将其抽象为一张图，从 $x$ 到 $x+1$ 有 $k$ 种方式，而 $x$ 到 $x+i+1$ 有 $1-k$ 种方案（是负数但是没关系）。求 $0$ 到 $n$ 的方案数。这可以通过枚举 $x\rightarrow (x+i+1)$ 这个动作进行了多少次来做到 $\mathcal{O}(\dfrac{n}{i})$，即：
$$ s_{i,n}=\sum_{c=0}^{\left\lfloor\frac{n}{i+1}\right\rfloor} \binom{n-ic}{c}k^{n-(i+1)c}(1-k)^{c} $$
对每一个 $i$ 求出 $s_{i,n}$ 和 $s_{i,n-1}$ 作差，根据调和级数，复杂度是 $\mathcal{O}(n\log n)$。
$\texttt{T3}$
咕咕咕
2021.04.18
$\texttt{Location:NOI2021}$
得分：$\texttt{210/300,Rank3}$。
[04.18]-错误
$\texttt{T3}$ 压根没去想，还是不能消极考试才行......
[04.18]-部分正解
$\texttt{T1}$
考虑右端点的右移，然后看左端点的合法情况。
直接激活线段树。时间复杂度 $\mathcal{O}(n\log n)$。
$\texttt{T2}$
起点终点很多很烦人，加两个虚点连接一下。
观察发现，把这两个虚点也连起来，其中连接若干重边，需要求的东西就变成了一条欧拉回路，从虚点开始。
然后上 $\text{BEST}$ 定理即可。复杂度 $\mathcal{O}(n^3)$。
$\texttt{T3}$
观察一个合法状态长什么样子。应该可以发现是一个类似菱形的东西：中间凸出两边凹陷。因此，可以考虑对这个东西做 $\text{dp}$。实际上只需要记录左侧、右侧分别属于菱形的上半部分还是下半部分就可以了。
需要前缀和优化 $\text{dp}$。