rddccd的博客

博客

The 2024 ICPC Asia East Continent Online Contest (I) 部分部分题解

2024-09-17 18:39:41 By rddccd

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}-1r_{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.

不会

rddccd Avatar