【题解】CCPC Wannafly Camp Day5

Note: Some problems have been weakened.

A、 Alternative Accounts

There are at most $3$ contest. We consider the hardest case that $k=3$ . For each account, we
compute the set of contests it participated in.
Let $\operatorname{cnt}_{S}(S \subseteq\{1,2,3\})$ be the number of accounts whose participated contest is set .
It is easy to see for an account that participated in the contests $\{1,2,3\}$ , it can't participate other contests.
For an account that participated in the contest $\{1,2\}$ , it can match with an account that only participated in the contest $\{3\}$ . It's the same for $\{1,3\}$ and $\{2,3\}$ .
For the remaining account, we need $\max \left(\operatorname{cnt}_{\{1\}}, \operatorname{cnt}_{\{2\}}, \operatorname{cnt}_{\{3\}}\right)$ peoples.

B、 Bitset Master

First, let's see how to compute the size of $S_{u}$ . When two sets $S_{u}$ and $S_{v}$ merge, the size becomes $\left|S_{u}\right|+\left|S_{v}\right|-\left|S_{u} \cap S_{v}\right|$ . We can see $S_{u} \cap S_{v}$ is exactly the set when these two sets merged last time. So we can compute it in $O(n+m)$ .
For the original problem, we can solve the problem backward. The meaning of the set $S_{u}$
becomes which vertices that $u$ can reach.

C、 Self-Adjusting Segment Tree

For a query $[l, r]$ and a vertex $[L, R]$ on the segment tree

If $[L, R]$ intersects with $[l, r]$ and $[L, R]$ is not included in $[l, r]$ , it will contribute to the number of visited vertices by $1$ .
If $[L, R]$ is included in $[l, r]$ and $L \neq R$ , it will contribute to the number of visited vertices by $-1$ .
If $[L, R]$ is included in $[l, r]$ and $L=R$ , it will contribute to the number of visited vertices by $1$ .
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 $[l, r]$ ).
We can use the partial sum technique to compute the contribute of each pair $[L, R]$ , denoted as $w_{L, R}$ .
Let $d p_{L, R}$ be the minimum total contributition of a subtree with the root $[L, R]$ , $d p_{L, R}=\min \left(d p_{L, k}+d p k+1, R+w_{L, R}\right)$

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 $3$ elements in $A$ and calculate the fourth element in $O(1)$ .

F、 Inversion Pairs

Let $dp_{i,j}$ be the number of permutations with $i$ elements and $j$ inverse pairs, $d p_{i, j}=\sum_{k=0}^{i-1} d p_{i-1, j-k}$
The answer $f_{i}=\sum_{j=0}^{i(i-1) / 2} d p_{i, j} j^{k}$ . We can compute first $O\left(k\right)$ terms in $O\left(k^{3}\right)$ .
We can prove sequence $\left\{f_{n} /(n-2 k) !\right\}$ is a polynomial, thus we can compute first terms and find $n$ -th term by interpolation.
However, CaiDui said $\left\{f_{n} /n !\right\}$ 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 $\Theta(\sqrt{p})$ term and the minimum value can become $O(\sqrt{p})$ . 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 $O(\sqrt{p})$ .

H、 Geometry PTSD

First, let's see how to compute the distance $d$ from $O$ to plane $ABC$ . We can compute the volume $V$ of $ABC$ by the determinant. Then we have $\frac{S d}{3}=V$ , where $S$ is the area of triangle $ABC$ , 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.
图片说明