时间安排

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