XXI Open Cup named after E.V. Pankratiev. Grand Prix of Nizhny Novgorod
A. Assignment Problem
暴力 $m!$ 枚举先后顺序，用 dfs 枚举，即可 $O(m)$ 判断新加的那个是谁。
时间复杂度 $O(m!\times m)$。
B
C. Multiple?
答案为 $\varphi(n)\binom{n-1}{k-1}$。
计算组合数数可以直接暴力。
D. Output Limit Exceeded
当 $i\leq \frac{n}{2}$，且 $[n-i+1,n]$ 内出现了两个或以上的质数时，答案一定为 $0$。
而当 $i>\frac{n}{2}$ 时，中间会有些重复的部分。我们完全可以让重复的部分一一对应匹配，因为若 $x\rightarrow y,y\rightarrow z$，那么可以变成 $x\rightarrow z,y\rightarrow y$。那么，此时 $i$ 的答案与 $n-i$ 完全相同。
在 $10^{18}$ 内，两个质数相隔的距离不多，那么直接KM或者网络流暴力求出 $0\sim k$ 的答案，其中 $[n-k+1,n]$ 内出现了两个质数，且 $k$ 最小。
使用网络流，时间复杂度 $O(k^{2.5}\log k)$。
E. Smol Vertex Cover
先用带花树求出一个一般图最大匹配 $M$。设最小点覆盖所需点数为 $C$。
显然有，$M\le C$，而题目要求 $C\le M+1$。
- $C=M$
对于每条在最大匹配内的边，都有且仅有一个点是选的；对于不在最大匹配内的边的点，两个至少选一个。
有且仅有相当于 $i\oplus j=1$，至少选一个相当于 $i\text{ or }j=1$。2-SAT。
- $C=M+1$
枚举哪个点是必须选择的，然后和 $C=M$ 的情况类似，判断的时候也做一遍 2-SAT即可。
总的时间复杂度 $O(n^3)$。
G. Remove the Prime
因式分解后，变成简单的取石子游戏。
Pollard-rho分解即可。
H. Excluded Min
I. Trade
重要性质：$p_i$ 均不一样。
假设要选某些纪念品，那么一定是将这些纪念品的 $p$ 从大到小排序后依次选择。
那么总的和即为 $\sum_{i=1}^kc_i+(i-1)p_i\le k+\sum_{i=1}^k(i-1)(k-i+1)\le O(\frac{k^3}{6})$，那么最多就选 $O((6S)^{\frac{1}{3}})$ 个物品。
排序，暴力DP。
J. Increasing or Decreasing
先对整个序列进行一遍从小到大的排序，然后假设前 $i-1$ 个已经找到，找到 $b_i$ 所在位置，然后看是最大值还是最小值。使用 $n-1$ 次，剩下最后一个不用管它。加上先前的整个排序，刚好使用 $n$ 次。
时间复杂度 $O(n^2\log n)$。
L. Extreme Wealth
答案为 $\frac{2^{a+b}}{\binom{a+b}{a}}$，即 $\frac{2^{a+b}a!b!}{(a+b)!}$。
$a,b$ 小的时候随便算，我们只考虑 $a,b$ 很大的情况。
考虑 $a=b$ ，此时阶乘用斯特林公式近似算。得到 $\frac{2^{a+a}a!a!}{(a+a)!}=\sqrt{\pi a}$。
设答案为 $S(a,b)$，考虑从 $S(a,b-1)$ 推导出 $S(a,b)$，其中 $a<b$，有：
$S(a,b)=\frac{2b}{a+b}S(a,b-1)$。
随着 $b$ 越来越大，$\frac{2b}{a+b}$ 越来越接近 $2$，这样很快就可以超出 $10^9$了，暴力模拟即可。
M. Discrete Logarithm is a Joke
签到题。知道了 $a_{10^6}$ 后，倒推即可。