2/14考试总结

时间安排

7:30–7:50 看题,T1可能是个数据结构之类的东西，T2是 dp ，T3 构造。
7:50–8:20 T3,仿照样例的构造，可以通过一部分测试点。
8:20–9:20 T1,发现题目实际上要求子树内各儿子的深度信息，可以 dsu ，对于不能暴力统计的部分可以打个懒标记维护。然后对拍。虽然带个 log 但是能过。
9:20–11:00 T2,发现必胜条件为存在某一长度大于一个下界的同一颜色的段，于是可以对段做 dp 。对于 k<=50 的部分，可以矩阵快速幂优化。思考 k^2=n 的部分分，发现可以容斥，尝试去写，发现答案不太对。
11:00–12:00 T3,尝试另一种构造，在纸上乱试，然后试出来一个貌似很对的，测试点貌似都能通过。

回顾反思

100+40+100
T1：
一部分时间花在了对拍上，调整参数加强数据强度。
调试时遇到的一个问题是，在划分轻重儿子的时候，忘记把儿子的sz加到部分上来更新 sz ,导致所有点 sz 都是 1 ，这种错误决不能再犯。
考场上写的是 dsu 的做法，考虑对重儿子最大深度与轻儿子最大深度之间差的部分打标记；长剖的做法思想类似，可以对 fi,j 记录其最后一次更新的结点离该链叶子的距离 len ,那么在根 x 时，需要更新的便是 lenx-len 的这一段。

T2:
考试的时候准备冲 70 来着,然后容斥的档没冲出来，拿了 40 。
想到了其中不需要多项式的容斥的部分分，但是一直调不出来，赛后发现是自己容斥的时候忘记乘上 (-1) 的系数。
需要注意的点是，要仔细阅读数据范围，该题中模数最大只有 1e7 级别，于是能够暴力处理1e7 以内的阶乘和其逆元，然后用lucas 快速计算极大数的组合数；如果没有注意到这一点，对极大数计算组合数就只能相对暴力求了，复杂度会很高。
该题实际上是要求将 n 划分为若干长度不小于某个限制的方案数，且划分有固定的权值，求权值积。
对于限制 lim ，对其数据范围分治，若 lim 较大，那么可以容斥钦定大于 lim 的段，复杂度是 $\frac{n}{lim}$ ；如果 lim 较小，则可以用特征多项式快速幂求解，暴力卷积是 $li{m}^2\log n$ 的。
一个之前不太会的知识点是利用特征多项式求常系数线形齐次递推某一项的答案，
例如有 $f_k=f_{k-1}+f_{k-2}+...+f_0$ ，那么有特征多项式 $x^k-x^{k-1}-x^{k-2}-...-1$ ，计算出头 k 项的值，求解 $x^n\mathrm{mod}{x}^k-x^{k-1}-x^{k-2}-...-1$ ，即可得到第 n 项的解。
具体可参考博客

T3:
正解没有给出构造，给了个随机调整法。
能放就随机放皇后，不能放随机一个限制小的位置，将控制它的皇后放到该位置。
然后随机跑上个 100 s，能过 n=5000 。

T2 的容斥是比较经典的。起码应该可以拿到 100+70+100=270+ 分左右