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\) 的限制，每个点的方案就是一个生成函数，记录为 \(\dfrac{f_i}{g_i}\) 。

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

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

JJLeo's solution

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

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

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

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

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

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

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

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

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

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

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

设 \(S=\max \limits _{i=1}^n s_i\)，\(C=\max \limits _{i=1}^n c_i\)，总时间复杂度是 \(O\big (C(nS)^2+q(nS)^2 \log w \big)\)。

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 * (1 + \cdots + 2i - 1) + (1 + \cdots + 2i - 1)\]

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

\(g_i = \sum\limits_{j=1}^{i - 1}p[j] + \sum\limits_{j = i}^{n}p_ig_i, f_i = 3\sum\limits_{j = 1}^{i - 1}p[j] + 2\sum\limits_{j = i}^{n}p_ig_i + \sum\limits_{j = i}^{n}p_if_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 \limits _{i=1}^nd_i=2k}\binom{k-1}{d_1-1,d_2-1,\cdots,d_{k+1}-1} \prod_{i=1}^n {a_i}^{d_i} \]

设生成函数：

\[ \begin{aligned} f_{a}(x) =& \sum_{i=1}^{+\infty}\frac{1}{(i-1)!}a^ix^i \newline =& \sum_{i=1}^{+\infty}\frac{1}{(i-1)!}{(ax)}^i \newline =& ax\sum_{i=0}^{+\infty}\frac{1}{i!}{(ax)}^i \newline =& axe^{ax} \newline \end{aligned} \]

则最终答案为：

\[ \begin{aligned} & \left[x^{2k}\right](k-1)!\prod_{i=1}^{k+1}f_{a_i}(x) \newline =& \left[x^{2k}\right](k-1)!\prod_{i=1}^{k+1}a_ixe^{a_ix} \newline =& \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_ix}\right) \newline =& \left[x^{2k}\right](k-1)!\left(\prod_{i=1}^{k+1}a_i\right)x^{k+1}e^{\left(\sum \limits _{i=1}^{k+1}a_ix\right)} \newline =& \left[x^{k-1}\right](k-1)!\left(\prod_{i=1}^{k+1}a_i\right)e^{nx} \newline =& (k-1)!\left(\prod_{i=1}^{k+1}a_i\right)\frac{n^{k-1}}{(k-1)!} \newline =& n^{k-1}\left(\prod_{i=1}^{k+1}a_i\right) \newline \end{aligned} \]

因此只需求出所有可能的 \(\left(\prod \limits _{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 \limits _{\sum\limits_{i = 1}^{n}a_i = D}\dfrac{D!}{\prod\limits_{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\limits_{i = 1}^{n}a_i = D + nk}\dfrac{(D + nk)!}{\prod\limits_{i = 1}^{n}a_i!}\dfrac{D!}{(D + nk)!} $$ 此时 \(a_i \ge k\) ，因此考虑容斥，我们只需要考虑有 \(i\) 个数小于 \(k\)，和为 \(j\) 的个数有多少个，贡献即可 \(O(1)\) 计算。个数可以直接用背包计算。

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

H

solved by JJLeo 2sozx

题意

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

现在给定 \(a_1,a_2,\ldots,a_n\)，定义

\[ b_i=\sum_{1 \le j,k \le n,j \otimes k = i} a_jk^c \]

求 \(b_1,b_2,\ldots,b_n\)。(\(1 \le n \le 10^6\))

题解

\[ x \otimes y=\prod _i p_i^{|a_i-b_i|}= \frac{xy}{\gcd^2(x,y)} \]

\[ \begin{aligned} b_i&=\sum_{1 \le j,k \le n,j \otimes k = i} a_jk^c \newline &=\sum_{\frac{jk}{\gcd^2(j,k)}=i} a_jk^c \newline &=\sum_{\frac{jk}{d^2}=i,d=\gcd(j,k)} a_jk^c \newline &=\sum_{d=1}^n\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[jk=i,\gcd(j,k)=1]a_{jd}{(kd)}^c \newline &=\sum_{d=1}^nd^c\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[jk=i,\gcd(j,k)=1]a_{jd}k^c \end{aligned} \]

设：

\[ 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^cf\left(j,\min\left(\left\lfloor\frac{n}{j}\right\rfloor,\left\lfloor\frac{n}{k}\right\rfloor\right)\right) \]

\(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突然想到了奇怪的运算符等价于乘积除以 \(\gcd^2\)，然后 15 分钟极限推式子 + 写代码，就过了，最后终于过稳定过过题了，不容易。

总结

Dirt

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