2021牛客暑期多校第四场

排名	当场过题数	至今过题数	总题数
26/1292	8	10	10

A

upsolved by JJLeo 2sozx

题意

$n$ 个节点的树形背包，每个节点物品权值为 $s_i$，可以选任意数量的物品，但每个节点要求该子树所选物品数量不能小于 $c_i$。

$q$ 次询问，选恰好权值为 $w$ 的方案数有多少？

($1\le n\le 100$，$1\le s_i\le 5$，$0\le c_i\le 150$，$1\le q\le 10$，$0\le w\le {10}^8$)

题解

2sozx's solution

显然如果不考虑 $c_i$ 的限制，每个点的方案就是一个生成函数，记录为 ${\displaystyle \frac{f_i}{g_i}}$ 。

考虑 $c_i$ 这个限制，对于 $g_i$ 求逆与 $f_i$ 乘起来，删掉前 $c_i-1$ 项的系数即可，考虑去维护这个 ${\displaystyle \frac{f_i}{g_i}}$ ，考虑通分，然后用 $f_i$ 减即可，多项式项数维护到 $n\times max(c)$ 即可，大点也能过。

考虑对于根的多项式，可以通过 $BM$ 来计算 $w$ 大的值，对于 $w$ 很小的值需要直接用多项式来算，因为前面的数并不是一个完全的多项式，而是删来删去得到的多项式，复杂度 $O($能过$)$

JJLeo's solution

如果不考虑 $c_i$ 的限制，每个节点的生成函数就是 ${\displaystyle \frac{1}{1-x^{s_i}}}$，子树的生成函数就是把子树里所有点的生成函数乘起来。

对于 $c_i$ 的限制，考虑 dfs 完一个子树时把当前生成函数的低于 $c_i$ 次项全部删掉，那么对于每个子树的生成函数一定也是形如 ${\displaystyle \frac{f_i(x)}{g_i(x)}}$ 的。我们可以维护分别维护分子和分母，然后求出 $h_i(x)={\displaystyle \frac{f_i(x)}{g_i(x)}}mod{x}^{c_i}$，得到新的分子 $f_i(x)-g_i(x)h_i(x)$。这里有两种方式求出 $h_i(x)$：

• 多项式求逆。
• 注意到 $g_i(x)$ 形如 ${\displaystyle \frac{1}{\prod _j(1-x^{s_j})}}$ 的形式，因此对 $f_i(x)$ 的前 $c_i$ 项做 01 背包的逆变换即可。

本题数据范围小，后者常数小，说不定比前者快，而且只需要三行，老好写了。

最后，需要用到线性递推与其对应生成函数的本质：

设 ${\displaystyle \frac{f(x)}{g(x)}}=h(x)$​​，$\mathrm{deg}f<\mathrm{deg}g$​​，当 $n\ge \mathrm{deg}g$ ​ 时：

$$\left[x^n\right]f(x)=0=\sum _{i=0}^{\mathrm{deg}g}\left[x^{n-i}\right]h(x)\left[x^i\right]g(x)$$

因此，对 $g(x)$ 进行移项归一化等调整就可以得到线性递推系数，递推的初值即为 ${\displaystyle \frac{f(x)}{g(x)}}$ 前 $\mathrm{deg}g$ 项。

注意到根节点的生成函数 ${\displaystyle \frac{f_1(x)}{g_1(x)}}$ 有可能出现 $\mathrm{deg}{f}_1\ge \mathrm{deg}{g}_1$，这样 $f$ 除以 $g$ 后会得到一个 $\mathrm{deg}f-\mathrm{deg}g$ 项的多项式，这说明前 $\mathrm{deg}f-\mathrm{deg}g$ 项并不能作为递推初值。

懒得写多项式除法，因此设 $m=max(\mathrm{deg}{f}_1,\mathrm{deg}{g}_1)$，用同样的 01 背包逆操作求出其前 $m$ 项，之后取前 $m$ 项的后 $\mathrm{deg}{g}_1$ 项作为递推初值即可。

当时没有理解透彻，还去 BM 求递推系数，老蠢蛋了。

设 $S=\underset{i=1}{\overset{n}{max}}{s}_i$，$C=\underset{i=1}{\overset{n}{max}}{c}_i$，总时间复杂度是 $O(C(nS{)}^2+q(nS{)}^2\log w)$。

B

solved by JJLeo 2sozx

题意

无限选 $[1,n]$ 的正整数，各有概率 $p_i$，如果这次选的数比之前最大的数小则结束，否则继续选，求游戏轮数平方的期望。($1\le n\le 100$ )

题解

2sozx's solution

考虑将平方变为每一次增加一个等差数列的贡献，即 $1+\cdots +2i-1=i^2$，这样如果在这个序列前面加一个数，总贡献变为

$$1+2\ast (1+\cdots +2i-1)+(1+\cdots +2i-1)$$

这样我们只需要维护总贡献 $f_i$，以及单位贡献 $g_i$ 即可转移。

$g_i=\sum _{j=1}^{i-1}p[j]+\sum _{j=i}^n{p}_i{g}_i,f_i=3\sum _{j=1}^{i-1}p[j]+2\sum _{j=i}^n{p}_i{g}_i+\sum _{j=i}^n{p}_i{f}_i$

复杂度为 $O(n)$。

不知道为啥n这么小

JJLeo's solution

考虑求出第一个数选 $i$ 的 轮次平方的期望 $f_i$ 及 轮次的期望 $g_i$，那么由 $f_j$ 转移到 $f_i$ ($j>i$) 相当于 $f_j$ 中每次的贡献都增加了 $2$，因此加上 $2g_j$ 即可，$g_j$ 到 $g_i$ 的转移则很简单就不赘述了。

最后转移方程写出来移个项就可以得到一个 $O(n)$ 的递推式了。

D

upsolved by JJLeo

题意

给定一颗 $n$ 个节点的树，删去 $k$ 条边，新增 $k$ 条边，使得新图还是一颗树，求方案数。($2\le n\le 5\times {10}^4$，$1\le k\le min(100,n-1)$)

题解

显然删掉 $k$ 条边会分出 $k+1$ 个连通块，设第 $i$ 个连通块有 $a_i$ 个点，根据 prufer 序列，答案为：

$$\sum _{\sum _{i=1}^n{d}_i=2k}(\genfrac{}{}{0ex}{}{k-1}{d_1-1,d_2-1,\cdots ,d_{k+1}-1})\prod _{i=1}^n{a_i}^{d_i}$$

设生成函数：

$$\begin{array}{rl}{f}_a(x)=& \sum _{i=1}^{+\mathrm{\infty }}\frac{1}{(i-1)!}{a}^i{x}^i\\ =& \sum _{i=1}^{+\mathrm{\infty }}\frac{1}{(i-1)!}{(ax)}^i\\ =& ax\sum _{i=0}^{+\mathrm{\infty }}\frac{1}{i!}{(ax)}^i\\ =& ax{e}^{ax}\end{array}$$

则最终答案为：

$$\begin{array}{rl}& \left[x^{2k}\right](k-1)!\prod _{i=1}^{k+1}{f}_{a_i}(x)\\ =& \left[x^{2k}\right](k-1)!\prod _{i=1}^{k+1}{a}_{i}x{e}^{a_{i}x}\\ =& \left[x^{2k}\right](k-1)!\left(\prod _{i=1}^{k+1}{a}_i\right)x^{k+1}\left(\prod _{i=1}^{k+1}{e}^{a_{i}x}\right)\\ =& \left[x^{2k}\right](k-1)!\left(\prod _{i=1}^{k+1}{a}_i\right)x^{k+1}{e}^{\left(\sum _{i=1}^{k+1}{a}_{i}x\right)}\\ =& \left[x^{k-1}\right](k-1)!\left(\prod _{i=1}^{k+1}{a}_i\right)e^{nx}\\ =& (k-1)!\left(\prod _{i=1}^{k+1}{a}_i\right)\frac{n^{k-1}}{(k-1)!}\\ =& n^{k-1}\left(\prod _{i=1}^{k+1}{a}_i\right)\end{array}$$

因此只需求出所有可能的 $\left(\prod _{i=1}^{k+1}{a}_i\right)$ 的和，到这里都是做过的原题 ARC106F，然后赛时卡死不会求了，寄。

考虑这个积的含义就是将树分为 $k+1$ 个连通块，每个连通块各选一个点的方案数，因此就转化为了简单的树形背包，设 $f_{i,j,0/1}$ 表示以 $i$ 为根的子树，不算当前连通块选了 $j$ 个连通块，当前连通块是否选了一个点，最后答案就是 $f_{1,k,1}$。

总时间复杂度为 $O(nk)$。

G

solved by JJLeo 2sozx

题意

求$\sum _{\sum _{i=1}^n{a}_i=D}{\displaystyle \frac{D!}{\prod _{i=1}^n(a_i+k)!}}$，其中 $a_i\ge 0$。

($1\le n\le 50$，$0\le k\le 50$，$0\le D\le {10}^8$)

题解

假设 $k=0$ ，式子等价于 $a_i$ 表示数字 $i$ 选择了几次，一共有 $D$ 个位置的所有排列，这个又等价于长度为 $D$ 的数组，每个位置可以选择 $n$ 个数，答案即为 $n^D$。

考虑转化式子，将其变为

$$\sum _{\sum _{i=1}^n{a}_i=D+nk}{\displaystyle \frac{(D+nk)!}{\prod _{i=1}^n{a}_i!}}{\displaystyle \frac{D!}{(D+nk)!}}$$ 此时 $a_i\ge k$ ，因此考虑容斥，我们只需要考虑有 $i$ 个数小于 $k$，和为 $j$ 的个数有多少个，贡献即可 $O(1)$ 计算。个数可以直接用背包计算。

另外还需要考虑这些不合法数字所占的位置，也是一个组合数，乘上即可，没乘这个 WA 了一发。

H

solved by JJLeo 2sozx

题意

设 $x=\prod _i{p}_i^{a_i}$，$y=\prod _i{p}_i^{b_i}$，定义一种新运算： $$x\otimes y=\prod _i{p}_i^{|a_i-b_i|}$$

现在给定 $a_1,a_2,\dots ,a_n$，定义

$$b_i=\sum _{1\le j,k\le n,j\otimes k=i}{a}_j{k}^c$$

求 $b_1,b_2,\dots ,b_n$。($1\le n\le {10}^6$)

题解

$$x\otimes y=\prod _i{p}_i^{|a_i-b_i|}=\frac{xy}{\stackrel{2}{gcd}(x,y)}$$

$$\begin{array}{rl}{b}_i& =\sum _{1\le j,k\le n,j\otimes k=i}{a}_j{k}^c\\ & =\sum _{\frac{jk}{\stackrel{2}{gcd}(j,k)}=i}{a}_j{k}^c\\ & =\sum _{\frac{jk}{d^2}=i,d=gcd(j,k)}{a}_j{k}^c\\ & =\sum _{d=1}^n\sum _{j=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{k=1}^{\lfloor \frac{n}{d}\rfloor }[jk=i,gcd(j,k)=1]a_{jd}{(kd)}^c\\ & =\sum _{d=1}^n{d}^c\sum _{j=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{k=1}^{\lfloor \frac{n}{d}\rfloor }[jk=i,gcd(j,k)=1]a_{jd}{k}^c\end{array}$$

设：

$$f(j,k)=\sum _{i=1}^k{a}_{ij}{i}^c$$

原式化为：

$$b_i=\sum _{j=1}^n\sum _{k=1}^n[jk=i,gcd(j,k)=1]k^{c}f(j,min(\lfloor \frac{n}{j}\rfloor ,\lfloor \frac{n}{k}\rfloor ))$$

$O(n\log n)$ 枚举合法的 $(j,k)$，再用 $O(\log n)$ 判断 $gcd$ 是否为 $1$。

另外枚举外层 $j$ 时预先处理出所有的 $f(j,\times )$，这部分复杂度也是 $O(n\log n)$ 的。

总复杂度是 $O(n{\log }^{2}n)$ 的，场上乱冲过了，据说这个值域有预处理后 $O(1)$ 求 $gcd$ 的黑科技。

记录

0h：看F过的人贼多CSK、ZYF想F，MJX乱看，然后ZYF挂了一发，发现把 i 写成了 x，改了就过了，之后MJX把J写了，CSK给MJX讲了个C的做法，太对了就去写了，MJX喂了ZYF一个I的正解，MJX脑子一抽把正解改假了又给了ZYF，寄了一发，C第一发也寄了。

1h：MJX重写了个I，过了，CSK改了改C也过了，ZYF看E是个经典算法，又TMD被卡常了，改了改就过了，MJX旁边搁那儿推B式子，没用期望推属实是个小可爱。

2h：ZYF E写完了推了推B就推出来了，MJX直接爬去看G，改吧改吧式子喂给了ZYF，ZYF直接冲锋，然后忘记选位置还要乘一个组合数，改了就过了。

3h：ZYF看D就是个原题，prufer 序列推出了式子，硬往树形背包上靠但就是不会做，MJX想了个意义，大概差不多，有点歪，然后被ZYF日掉了，实际上是正解，之后就感觉不可做了。

4h：开始看我们开始觉得一点都不可做的H题，先乱想 + 打表浪费了半个小时，4.35 的时候MJX突然想到了奇怪的运算符等价于乘积除以 $\stackrel{2}{gcd}$，然后 15 分钟极限推式子 + 写代码，就过了，最后终于过稳定过过题了，不容易。

总结

Dirt

F(+1)：ZYF X战警
I(+1)：MJX要想的深一点，优化很有可能是错的
C(+1)：
E(+1)：卡常，stl慎用
G(+1)：逆元写错了