https://qoj.ac/blog/bulijiojiodibuliduo/blog/994 对杜老师skip的部分的部分补充

C.

首先$\pmod 2$意义下$per = det$，然后对整个矩阵做向后的差分，得到答案等于$det(M)$，其中$M_{i,l_{i}-1},M_{i,r_{i}}=1$。假设从$l_{i}-1$到$r_{i}$连边，则边代表左部点，边两端的点代表右部点，每条边选一个端点匹配。如果成环了，则环上的匹配可以交换方向，答案必为偶数。而$n+1$个点$n$条边的无环图必为树，对于树而言，以$0$为根（$0$不需要匹配），则每个点匹配到父亲的边，方案唯一。

D.

没想过，咕

I.

考虑最外层的若干个凸包，假设多于一个，则使用这些凸包的凸包代替这些凸包，显然点数减少，体积增大，且不影响内部方案。所以一层层剥凸包是最优的。

J.

每次只能选$a_{i}>0$很讨厌，不如假设每次谁都能选好了！但是只有选中了$a_{i}>0$的才对次数有一次贡献。不妨枚举前$c$个人中最后一个被干掉的人$p$ ($1\le p \le c$)，然后考虑每次选中的人的序列的生成函数。令$x^iy^j$代表序列长度为$i$，有$j$次有效操作的序列，则:

$p$号人对应的gf是 $(x^{a_{p}-1}y^{a_{p}-1})$，代表选且仅选了$a_{p}-1$次（最后一次不算，被我们钦定了）

$1 \le j \le c , j \neq p$对应gf是 $\frac{x^{a{j}}y^{a_{j}}}{a_{j}!} + y^{a_{j}}(e^x - \sum_{k=0}^{a_{j}}{\frac{x^k}{k!}})$，代表至少要选择$a_{j}$次，并且有效选择次数一定是$a_{j}$。

$j > c$对应的gf是 $\sum_{k=0}^{a_{j}}{\frac{x^ky^k}{k!}} + y^{a_{j}}(e^x - \sum_{k=0}^{a_{j}}{\frac{x^k}{k!}})$，选几次随意，但是如果选的次数少于$a_{j}$则都是有效的，否则就有$a_{j}$次有效选择。

不妨令$e^x$为第三维的$z$，将所有gf乘起来之后，考虑$x^iy^je^{kx}$这一项，代表了有效选择次数为$j+1$(额外算上最后一个被我们钦定的)，其对应概率为$\sum_{t\ge 0} {\frac{k^t(t+i)!}{t!n^{i+t+1}}} = \frac{i!}{(n-k)^{i+1}}$（考虑无穷和式展开后每一个$x^{i+t}$前的系数，以及其对应的序列概率即可），将所有贡献累计即为答案。

每次暴力做乘法的话复杂度是$O(n^5a^3)$，如果先乘起来然后对每个$p$做除法是$O(n^4a^3)$，实测暴力做就可以通过。

PS:好像有不需要枚举$p$的做法，但是不会，有没有教教我啊？

K.

不会