补题情况
| 题目 | 蒋贤蒙 | 王赵安 | 王智彪 |
|---|---|---|---|
| A | 0 | 0 | 0 |
| B | 0 | 0 | 0 |
| C | 2 | 0 | 0 |
| D | 0 | 0 | 0 |
| F | 0 | 0 | 0 |
| G | 0 | 0 | 0 |
| I | 0 | 0 | 2 |
| J | 0 | 0 | 2 |
题解
C. Cells
题意
给定一个二维平面，求满足如下条件的 $n$ 元路径组个数：
- 第 $i$ 条路径 $(a_i,0)\to (0,i)$
- 每次移动只能选择 $(x,y)\to (x-1,y),(x,y+1)$
数据保证 $a_{i-1}\lt a_i$。
题解
显然有
$$ M= \begin{bmatrix} {a_1+1\choose 1}&{a_1+2\choose 2}&\cdots&{a_1+n\choose n}\\ {a_2+1\choose 1}&{a_2+2\choose 2}&\cdots&{a_2+n\choose n}\\ \vdots&\vdots&\ddots&\vdots\\ {a_n+1\choose 1}&{a_n+2\choose 2}&\cdots&{a_n+n\choose n}\\ \end{bmatrix} = \prod_{i=1}^n \frac 1{i!} \begin{bmatrix} \frac {(a_1+1)!}{a_1!}&\frac {(a_1+2)!}{a_1!}&\cdots&\frac {(a_1+n)!}{a_1!}\\ \frac {(a_2+1)!}{a_2!}&\frac {(a_2+2)!}{a_2!}&\cdots&\frac {(a_2+n)!}{a_2!}\\ \vdots&\vdots&\ddots&\vdots\\ \frac {(a_n+1)!}{a_n!}&\frac {(a_n+2)!}{a_n!}&\cdots&\frac {(a_n+n)!}{a_n!}\\ \end{bmatrix} $$
设 $x_i=a_i+1$，则
$$ M= \prod_{i=1}^n \frac 1{i!} \begin{bmatrix} x_1&x_1(x_1+1)&\cdots&\prod_{i=0}^{n-1}(x_1+i)\\ x_2&x_2(x_2+1)&\cdots&\prod_{i=0}^{n-1}(x_2+i)\\ \vdots&\vdots&\ddots&\vdots\\ x_n&x_n(x_n+1)&\cdots&\prod_{i=0}^{n-1}(x_n+i)\\ \end{bmatrix} $$
从左到右用列消元，可以得到
$$ M= \prod_{i=1}^n \frac 1{i!} \begin{bmatrix} x_1&x_1^2&\cdots&x_1^n\\ x_2&x_2^2&\cdots&x_2^n\\ \vdots&\vdots&\ddots&\vdots\\ x_n&x_n^2&\cdots&x_n^n\\ \end{bmatrix} $$
每行都提出一个 $x_i$，就可以得到一个范德蒙行列式，于是有
$$ \det M=\prod_{i=1}^n \frac {a_i+1}{i!}\prod_{1\le i\lt j\le n}(a_j-a_i) $$
考虑 $\text{NTT}$ 计算每个值在 $\prod_{1\le i\lt j\le n}(a_j-a_i)$ 出现的次数。
具体的，可以设 $f(x)=\sum_{i=1}^n x^{a_i},g(x)=\sum_{i=1}^n x^{-a_i}$，则每个值 $k$ 出现次数就是 $[x^k]f(x)g(x)$。
注意还有 $i\lt j$ 的限制，根据对称性，考虑 $$然后做快速幂即可，时间复杂度 $O(V\log V)$。
I. Incentive Model
题意
有两个人争夺 $n$ 个物品，每一轮争夺一个物品，每次争夺都有成功概率。给定 $x,y$ 代表初始双方的 $stake$ 分别为 ${\frac x y}$ 和 $1-{\frac x y}$ ，每次争夺双方成功概率为自己的 $stake$ 比双方相加的 $stake$ ，然后每一轮如果第一个人获胜，他之后的 $stake$ 要加上 $w$ ，问第一个人争夺成功轮数的期望，结果对 $998244353$ 取模。
题解
我们设对于第一个人，第 $i$ 轮获胜的概率为 $X^{i}$ ，第 $i$ 轮的 $stake$ 期望为 $S_{i}$ 。
我们有 $S_{0}={\frac x y}$
然后我们有 $X_{i+1}={\frac {S_{i}} {1+w×i}}$ ， $S_{i+1}=S{i}+w×X_{i+1}$
所以有 $S_{i+1}=S_{i}+w×({\frac {S_{i}} {1+w×i}})=S_{i}×(1+{\frac w {1+w×i}})=S_{i}×{\frac {1+(i+1)×w} {1+i×w}}$
所以有 ${\frac {S_{i+1}} {1+(i+1)×w}}={\frac {S_{i}} {1+i×w}}=…={\frac {S_{0}} {1+0×i}}={\frac x y}$
所以有 $S_{n}={\frac x y}×(1+n×w)$
又因为获胜轮数可以表示为 ${\frac {S_{n}-{\frac x y}} {w}}$
所以化简得到答案为 ${\frac x y}×n$
J. Jam
题意
现在有 $N,W,S,E$ 四个方向，每个方向可以左拐右拐直走，然后会有一些互相撞车的情况，单位时间每个路线可以通过一辆车，我们要保证不能相撞，然后给出这十二个路来的车的量数，问最少多少时间能让所有的车都走完。
题解
由图显然右拐不用考虑，我们求出其他最长时间再分别和这四个数取 $max$ 就可以了，所以只需要求出满足剩下八个的最小的时间就好了。
然后有很多不是最优的情况不用考虑，比如从 $N$ 直走 和 从 $N$ 直走+从 $S$ 直走，前者的情况在任何情况下都不如后者显然不用考虑，于是我们就挑选最优的方案，可以找出十二种，最后的最优策略一定是这十二种的线性组合，我们分别设出他们的执行次数，然后就变成了八个不等式，每个不等式都是大于等于的关系，然后有十二个未知数。跑一个单纯型就结束了，然后对应的哪个未知数，自己画个图就好了。
当然这东西可能被卡？看了一眼题解，我们可以发现每一种方案都只对应两个情况，所以我们可以将他们代表的点连线然后我们发现这是一个多了两条边的二分图，枚举一下两条边选了多少次，剩下的跑网络流就好了。这个复杂度是 $O(n^{2}C),$ 其中 $C$ 是网络流复杂度。
