[June 29, 2022] examination summary

Time arrangement

7:30~8:20

First look at T1, I feel I can do better , Kouhu made a four-dimensional Mo team on the suffix tree to set the line segment tree , I feel I can rush .

8:20~9:30

Find out T1 Wrong question , So I went to see T2.
It feels like binomial inversion , Then preprocess some dp There is $O(n^3)$ 了 , Then use polynomial to accelerate to $O(n^{2}logn)$
So there is 60pts 了 .

9:30~10:00

Go back and think T1, It is found that as long as we build a suffix tree and match it greedily , There is 50pts 了 .

10:00~10:30

T3 There is an obvious $O(nT)$ Of dp, But from x Departure , So turn upside down dp That's it .

10:30~11:20

This Dp Obviously, matrix multiplication can be used to speed up , But matrix multiplication is $O(n^3)$ Of , Guess that there won't be too many valuable positions , And then I started writing , After writing for a while, I feel wrong , Then it's fake .