2022/6/9 exam summary

Time arrangement

7:40~8:00
Hit the watch and found T1 Laws ,n<=5000 Can be violent , The shape of the tree can enumerate the depth randomly , Then do it with the same depth ,60pts
8:00~8:20
Yes T2 Of 10pts Explosive search
8:20~8:50
See the spanning tree count and think prufer Sequence , set up dp[i][j] Before presentation i Put it at a point j The weight sum of times , Just enumerate how many transfers are selected ,30pts
9:00~9:15
Find out T2 The transfer of can be written as EGF The form of multiplication , And then I wrote a n^3 The violent convolution of , No problem found
9:20~10:00
hold EGF Take all ln Then add , Finally, exp, After thinking for a long time, I can't write how to deduce linearly ln(F(x)), Then I gave up
10:00~10:20
Wrote violent n Time NTT Of 50pts, Constant is a little big , Afraid of being stuck
10:20~11:00
Write T3 The violence of , I started with a $O(n^{2}Qlo{g}^{2}n)$ How to do it , Afraid of being stuck, I often don't write , After thinking for a while, I came up with a $O(Q{n}^3)$ How to do it , It can be achieved by further optimization $O(Q{n}^2)$, It's also very good to write
11:00~12:00
Want to T1 Sum of positive solutions of T2 Of ln The expansion of , But there is no progress