Note: Some problems have been weakened.

A、 Alternative Accounts

There are at most contest. We consider the hardest case that . For each account, we
compute the set of contests it participated in.
Let be the number of accounts whose participated contest is set .
It is easy to see for an account that participated in the contests , it can't participate other contests.
For an account that participated in the contest , it can match with an account that only participated in the contest . It's the same for and .
For the remaining account, we need peoples.

B、 Bitset Master

First, let's see how to compute the size of . When two sets and merge, the size becomes. We can see is exactly the set when these two sets merged last time. So we can compute it in .
For the original problem, we can solve the problem backward. The meaning of the set
becomes which vertices that can reach.

C、 Self-Adjusting Segment Tree

For a query and a vertex on the segment tree

• If intersects with and is not included in , it will contribute to the number of visited vertices by .
• If is included in and , it will contribute to the number of visited vertices by .
• If is included in and , it will contribute to the number of visited vertices by .
  Thus the contribution of a vertex only depends on the vertex ifself now, instead of the structure of the tree (whether its father is included in ).
  We can use the partial sum technique to compute the contribute of each pair , denoted as .
  Let be the minimum total contributition of a subtree with the root ,

D、 Circle Union

Recall the circle union algorithm, we need to find the border of the circle and find the answer.
In this problem, we can easily solve it in a similar way. For each piece of arcs on the circle, we just simply compute the probability that it's on the border and contribute it to the answer.

E、 Matching Problem

We can enumerate first elements in and calculate the fourth element in .

F、 Inversion Pairs

Let be the number of permutations with elements and inverse pairs,
The answer . We can compute first terms in .
We can prove sequence is a polynomial, thus we can compute first terms and find -th term by interpolation.
However, CaiDui said is a linear recurrence sequence, we can solve it by BerlekampMassey algorithm.

G、 Cryptographically Secure PRNG

We can regard the modulo inverse as a random sequence. If we compute the first term and the minimum value can become . Thus for the remaining term, we can enumerate the value and compute the position of the value to see if it is the minimum. The expected time complexity is .

H、 Geometry PTSD

First, let's see how to compute the distance from to plane . We can compute the volume of by the determinant. Then we have , where is the area of triangle , which can be computed stably.
Then we can try some constructions and test locally. One intuitive way is that find an equilateral triangle and make some numerical perturbations.

I、 Practice for KD Tree

is small, we can compute the entire matrix in . Then find the maximum by 2d segment tree.

J、Xor on Figures

We need to find the rank of binary vectors. It can be solved in by Gaussian elimination and bitset.