AC代码

C. Cells

给定大小为 $N$ 的数组 $A$ ，询问 $N$ 个人分别从点 $(0,A_i)$ 出发前往 $(i,0)$ 且路径不相交的方案数。

$N\leq 5\times 10^5, A_i\leq 10^6$ 。

光从题面考虑，这就是LGV引理的模板题，但是求行列式的复杂度高达 $N^2(N+\log MOD)$ ，因此难以直接解决本题。

但是我们可以通过LGV引理暴力打表，推出本题的公式为：

其中 $f_n$ 可以用递推式表示：$f_n=n!f_{n-1},f_1=1$ ，因此本题的难点就只剩下了 $\prod_{i=1}^N\prod_{j=i+1}^N (A_j-A_i)$ 的求解。

由于 $A_i\leq 10^6$ ，因此这个问题可以开一个 $1000001$ 的桶，然后用减法卷积求出所有 $A_j-A_i$ 的出现次数，然后 $O(N)$ 累加起来。

E. Eyjafjalla

首先树上二分找到温度能达到的最高节点，然后再将温度离散化，在树上跑dfs的过程中使用线段树维护可达节点的数量。

G. Glass Balls

树上dp，考虑每个节点是否为终结节点的情况，推出状态转移公式后可以发现，每个节点的儿子中最多只有一个非终结节点，根据这个要求可以求出转移概率。

H. Happy Number

题目本质为求解三进制下数的表示。

I. Incentive Model

比赛时猜结果为 $\frac{n\times x}{y}$ 就过了。

J. Jam

可以将问题转换为，将每条道路看作一个点，如果两条道路直接不冲突就可以建边。然后问题转换为图上求最多点对，就可以使用带花树解决。

总结

开场签H，然后合作解决E。J题一开始用贪心过不了，也想过网络流但建不出图，后来只能换成带花树。然后I题读完题后猜结论。C题的公式花了比较多的时间才解决，之后注意看A和G，G的dp公式有问题答案错误，A题解决方法不对出不了。