3/6考试总结

时间安排

7:30–7:50 看题，T1,T2 感觉是同类型的题，直接搜索状态然后 dp 一下，T3 估计是个独角晒。
7:50–8:20 T3，有 n^2 的式子，然后可以优化到 n ,写暴力验证一下发现不对。很迷，反复推了几遍都拍不上暴力。扭头看 T1,T2 了。
8:20–10:20 T1,显然只需要知道相对大小就可以了，搜索一下状态比较少，那么 dp 一下就行了。有一个贡献不是很好求推了一阵子。
10:20–11:10 T2,和前几天 ZR 非常像。打 zr 的时候有一个想法， zr 那个版本做不了，但是这道题明显比 zr 的那道若，可以直接用之前的想法做。先写部分分，状压一下，状态数大概有 250 左右，于是对于 m 小的时候暴力 dp 就行了。
11:10–11:40 T2，意识到这玩意可以矩乘。于是就有 状态数^3log 的做法。不过我还没有去减状态，有点卡。

回顾反思

T1:
这道题基本思想比较简单，但是花费时间有点长了。
主要是因为推导一个式子 $\sum _{a}C(a,c)C(K-a,d)=C(K+1,c+d+1)$ ，拍了几组是没问题的。
于是就和 K 具体大小无关直接做了，也没用到题解所说的拉格朗日插值。不过硬要上差值也是没问题的，贡献是形如 $C(K,n)$ 的形式，是 n 次或者 n+1 次多项式，n比较小，算几遍差值就行了。
T2:
基本思路没差。
但是我赛时没有尽可能地去减状态，于是状态数比较大就 T 了。
具体地，注意到答案只跟状态中若干段的长度有关，那么只要存长度就行了；进一步地，这玩意和若干长度的顺序也无关，对状态里的长度排一下序，状态数会更少。
T3：
赛时推导到某个地方卡住了。
主要是因为设 $D$ 替换形如 $ab$ 的式子的时候，忽略了 $a$ 被 $D$ 整除的条件，也就是少了个整除号，然后就错了。
赛时一直没发现，于是耽误了时间，也推不下去。
一定要注意。
然后就是独角晒求 $id\times \varphi$ 的前缀和。
比较关键的点是，
拿 $I$ 卷一下，于是 $id\times \varphi \times I=id\times id=\sum _{d|n}d\frac{n}{d}=n\cdot \sigma (n)$
其中 $\sigma (n)$ 为 n 的约数个数。