目录
补题情况
| 题目 | 蒋贤蒙 | 王赵安 | 王智彪 |
|---|---|---|---|
| A | 2 | 1 | 0 |
| B | 2 | 1 | 0 |
| C | 2 | 1 | 0 |
| D | 0 | 0 | 0 |
| F | 0 | 0 | 0 |
| G | 2 | 2 | 0 |
| I | 1 | 0 | 2 |
| J | 2 | 0 | 2 |
题解
A. A Math Challenge
题意
$$ \sum_{i=0}^n\sum_{1\le cj\le ai+b}i^pj^q $$
题解
设 $F(n)=\sum_{i=1}^n i^q$，于是上式转化为
$$ \sum_{i=0}^ni^pF(\lfloor \frac {ai+b}c\rfloor) $$
由于 $F(n)$ 是 $q+1$ 次多项式，所以高斯消元可以暴力求出 $F(n)$ 的表达式。于是问题转化为计算 $\sum_{i=0}^ni^p(\lfloor \frac {ai+b}c\rfloor)^k(0\le k\le q)$。
上式用万能欧几里得算法板子可以 $O\left(p^2q^2\log c\right)$，题目正解是类欧几里得算法 $O\left((p+q)^3\log c\right)$，不过卡卡常还是能过的。
B. Best Subgraph
题意
定义 $k-\text{degree}$ 子图为每个点在子图中度数至少为 $k$ 的连通极大子图。
定义每个 $G$ 的子图 $S$ 的分数为 $M\times m(S)-N\times n(S)+B\times b(S)$。
其中 $m(S)$ 表示 $S$ 的边数，$n(S)$ 表示 $S$ 的点数，$b(S)$ 表示 $|\{(u,v)|(u,v)\in G,u\in S,v\not\in S\}|$。
求分数最大的 $k-\text{degree}$ 子图，并求出分数最大的 $k-\text{degree}$ 子图中 $k$ 的最大值。
输入保证图连通。
题解
首先，定义 $V(k)$ 表示所有 $k-\text{degree}$ 子图的并集，易知 $V(k+1)\subseteq V(k)$。
构建分层图，其中第 $k$ 层的点集为 $V(k)-V(k+1)$，同时对每个点 $u\in V(k)-V(k+1)$，$w(u)=k$。
然后考虑按层加点，动态维护当前每个 $k-\text{degree}$ 子图的答案。对于每个新加入的点 $u$，首先他本身产生贡献 $-N$。
对于 $u$ 的所有连边 $(u,v)$，如果 $w(v)\gt w(u)$，则 $(u,v)$ 会被加入 $m(S)$，同时从 $b(S)$ 删除，产生贡献 $M-B$。
如果 $w(v)=w(u)$，则 $(u,v)$ 也会被加入 $m(S)$，但为了贡献被计算两次，于是每个点的贡献为 $\frac M2$。
如果 $w(v)\lt w(u)$，则 $(u,v)$ 会被加入 $b(S)$，产生贡献 $B$。
于是上述过程可以将所有贡献都转化为每个点的点权。考虑加入点时并查集维护每个连通块的点权和。
每层点全部加完后查询每个连通块的点权和的最大值即为所有 $k-\text{degree}$ 子图的最大答案。
至于如果计算每个点的 $w(u)$。首先输入保证图连通，所有图 $G$ 本身就是 $1-\text{degree}$ 子图。
考虑先删去所有度数为 $1$ 的点，删点后可能会导致原来度数不为 $1$ 的点度数不大于 $1$，继续删除，直到无点可删，得到 $2-\text{degree}$ 子图。
将删去的点的 $w(u)$ 全部设为 $1$，然后再求 $3-\text{degree}$ 子图不断重复上述过程，即可得到所有 $w(u)$。
时间复杂度 $O\left(\text{Na}(n+m)\right)$。
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$ 的限制，根据对称性，只考虑 $k\gt 0$ 的部分贡献然后做快速幂即可，时间复杂度 $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$ 是网络流复杂度。
