2022/6/9 考试总结

时间安排

7:40~8:00
打表发现了T1的规律，n<=5000可以暴力做，树的形态随机可以枚举深度，然后把同一个深度的一起做，60pts
8:00~8:20
写了T2的10pts爆搜
8:20~8:50
看到生成树计数想到prufer序列，设dp[i][j]表示前i个点放了j次的权值和，枚举这个点选了多少个转移就行了，30pts
9:00~9:15
发现T2的转移可以写成EGF相乘的形式，然后就写了个n^3的暴力卷积验证一下，发现没有问题
9:20~10:00
把EGF都取ln之后相加，最后再exp，想了半天写不出来怎么线性推出ln(F(x))，然后就放弃了
10:00~10:20
写了暴力的n次NTT的50pts，常数有点大，害怕被卡常
10:20~11:00
写T3的暴力，一开始写了个$O(n^{2}Qlo{g}^{2}n)$的做法，怕被卡常就没写，想了一会想出了一个$O(Q{n}^3)$的做法，再优化一下就可以做到$O(Q{n}^2)$，写起来也挺好写的
11:00~12:00
想T1的正解和T2的ln的展开式，不过都没有什么进展