2022/7/17 exam summary

Time arrangement

8:00~9:00

T1 First, we can find the ring length, and then the problem becomes how many $x\le n,y\le m,x^y\equiv 0(modp)$
And then enumerate p And then simply exclude it .
This part of the complexity $O(\sqrt{p}{2}^7)$ But I'm not satisfied with running

9:00~10:00

The bottleneck of the algorithm just now is to find the ring length , Consider writing the transfer in the form of a matrix , Then find $A\times B^t\equiv C(modp)$ The smallest t, It can be used BSGS, But due to the A,C The particularity of , There is no need to reverse . I hope I can

10:00~10:30

At the beginning with map Save the matrix , It's too slow , It was later changed to hash surface , Take off soon , But the space seems a little high , Because of this hash The table stores a matrix .

10:30~11:10

T2 There is one at a glance nmlogmlogn How to do it , It can be used 01BFS Remove one log, Can have 60 Divide up , Well written .

11:10~11:30

T3 No idea at all , Only written. 20pts violence .

12:00~12:30

Find out T2 There's a mistake , Change it quickly .

A summary after the exam

T1

Although my T1 We can do better , However, the author is better .
First, there is no need for a matrix BSGS, You can expand and enumerate directly according to the congruence $\phi (9p)$ Factor of , Judge whether the ring is long .
secondly , The positive solution is obtained by turning y Except come here , Give Way y The upper bound of is very small , When y When it is greater than the upper bound , Composite x The number of will not become .
So it is log Of . I feel like I'm doing problems , I don't like pushing , Always use something more routine or mindless , such as BSGS Or tolerance .
Still need to write more , Simplify the operation when necessary .

T2

I thought of reconstructing the tree during the exam , But I don't know how to judge whether the two intervals are reachable , The merging of line segments and trees of the problem solution is very wonderful , Maintain the reachable points in an interval , The rest is 60 Two points .

T3

The first step of transformation did not expect , I've been thinking dp/ Pull and insert , The result is a combinatorial number .
secondly , According to the small modulus, this kind of combination number is converted to Lucas On , Then similar to a P Decimal digits dp.
To be honest, I have just done a similar problem before [ Tsinghua training 2016] Combinatorial number problem , But it is much simpler than this question , There is no need to consider abdication or anything .