2021牛客暑期多校训练营4¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 45/1292（校内4/22） | 7 | 10 | 10 |
A¶
upsolved by Suspicious String
题意¶
有 \(n\) 个课程，每门课有学分 \(s_n\)，且每门课都可以选无数次，\(q\) 个询问，求选了恰好 \(w\) 学分的方案数。 题目还会给出一个培养方案：一个 \(n\) 个点的有根树，每个限制是 \(x\) 的子树里的课的学分总和至少为 \(c_x\)。
\(1\leq n\leq 100\)，\(1\leq s_n\leq 5\)，\(1\leq c_n\leq 150\)，\(1\leq q\leq 10\)，\(1\leq w\leq 10^8\)。
题解¶
首先可以得到以下朴素解法：
对于第 \(n\) 门课程，不考虑其他限制，可获得的学分数为 \(0,s_n,2s_n,\cdots\)。
各学分方案数的生成函数为 \(A_n(x)=\sum_{i=0}^\infty x^{s_ni}\)，其封闭形式为 \(1\over 1-x^{s_n}\)。
考虑培养方案的学分限制，对于第 \(n\) 门课程，设 \(F_n\) 为未考虑学分限制的生成函数，\(\bar F_n\) 为考虑学分限制的生成函数，可以得到下式：
\(F_n(x)=A_n(x)\prod_{i\in\text{son}_n}\bar F_i(x)\)
而 \(\bar F_n\) 只需清除 \(F_n\) 最低次的 \(c_n\) 项：
\(\bar F_n(x)=F_n(x)-F_n(x)\bmod x^{c_n}\)
遍历培养方案树即可计算得到根结点 \(\text{root}\) 的生成函数。
对于询问，给出学分数 \(w\)，\([x^w]\bar F_\text{root}\) 即为答案。
由于 \(w\) 可能取到 \(10^8\)，我们并没有办法直接求出 \(\bar F_\text{root}\) 的全部系数。
一种做法是注意到 \(A_n(x)\) 的形式，可以将所有 \(F_n(x)\) 写为 \(P_n(x)\over Q_n(x)\) 的形式，并且有：
\(\bar F_n(x)={\bar P_n(x)\over Q_n(x)}={P_n(x)-Q_n(x)(F_n(x)\bmod x^{c_n})\over Q_n(x)}\)
但是对于每个结点计算 \(\bar F_n\) 似乎比较繁琐，并且计算 \([x^w]{\bar P_\text{root}(x)\over Q_\text{root}(x)}\) 也并不容易操作，至少我不太会。
所以怎么办呢？一起来写一些显然易见的结论吧！
设下标以 \(0\) 开始的 \(k\) 阶线性递推数列 \(\{a_n\}\) 对于 \(i\geq k\) 满足下式：\(a_i=\sum_{j=1}^k a_{i-j}c_j\)
数列 \(\{a_n\}\) 的生成函数 \(A(x)\) 为：\(A(x)=\sum_{i=0}^\infty a_ix^i\)
由递推关系可以得到：\(A(x)=A(x)C(x)+A(x)\bmod x^k\)
其中 \(C(x)\) 为递推系数 \(\{c_j\}\) 的生成函数，即 \(C(x)=\sum_{j=1}^k c_jx^j\)
设 \(R(x)=A(x)\bmod x^k\)，解递推关系式可以得到：
\(A(x)={R(x)\over 1-C(x)}\)
容易知道 \(R(x)\) 成为数列 \(\{a_n\}\) 的前 \(k\) 项的生成函数当且仅当 \(\deg R<\deg C=k\)。
若 \(\deg R\geq \deg C\)，这意味着数列 \(\{a_n\}\) 并不是从第 \(k+1\) 项就满足递推式。
但可以将 \(A(x)\) 改写为 \(Q(x)+{R'(x)\over 1-C(x)}\)，其中 \(R'(x)=R(x)\bmod (1-C(x))\)，\(Q(x)={R(x)-R'(x)\over 1-C^2}\)，这将 \(\{a_n\}\) 写为一个从第 \(k+1\) 项起满足递推式的数列 \(\{a'_n\}\) 与一个 \(\deg R-\deg C+1\) 项的数列 \(\{b_n\}\)。
容易知道 \(R'(x)\) 成为数列 \({a_n}\) 的前 \(k\) 项的生成函数，\(Q(x)\) 为 \(\{b_n\}\) 的生成函数。
注意到当 \(deg R<deg C\) 时，形如 \(R(x)\over 1-C(x)\) 的多项式与线性递推数列一一对应。
如果我们分别有 \(k_a\) 阶与 \(k_b\) 阶线性递推数列 \(\{a_n\},\{b_n\}\)，令 \(d_n=\sum_{i=0}^{n-1}a_ib_{n-i}\)，则 \(\{d_n\}\) 也为线性递推数列。不妨设 \(A(x)={R_A(x)\over 1-C_A(x)},B(x)={R_B(x)\over 1-C_B(x)}\)，显然 \(D(x)={R_AR_B\over 1-(C_A+C_B-C_AC_B)}\)，这还说明 \(\{d_n\}\) 为 \((k_a+k_b)\) 阶线性递推数列。
对于 \(k\) 阶线性递推数列，我们只需要数列中连续的 \(k\) 个值即可推出数列中后续所有值，常系数线性齐次递推的细节略去。
因此将某个线性递推数列 \(\{a_n\}\) 的前 \(t\) 项删去，余下的 \(\{a'_n\}=\{a_{n+t}\}\) 仍为线性递推数列，并且线性递推关系不变。
由上述结论，易见对于所有课程，\(A_n(x), F_n(x), \bar F_n(x)\) 均对应线性递推数列。
更进一步地，设 \(\bar F_\text{root}(x)={\bar P_\text{root}(x)\over Q_\text{root}(x)}\)，设 \(f_n=[x^n]\bar F_\text{root}(x)\)，易见 \(Q_\text{root}(x)=\prod_{i=1}^n (1-x^{s_i})\)，从而可知 \(Q_\text{root}(x)\) 给出了 \(\{f_n\}\) 的递推关系式，并且 \(\{f_n\}\) 阶数为 \(\deg Q=\sum_{i=1}^ns_i\)。因此只需知道 \(\bar F_\text{root}(x)\) 的边界 \(\sum_{i=1}^ns_i\) 项即可对于任意给定的 \(w\) 求出 \(f_w\)。
遍历培养方案树，暴力维护多项式前 \(L=\max_{i=1}^n \{c_i\}+\sum_{i=1}^n s_i\) 项未删去项，无论系数有无意义。多项式乘法不变，但在删去 \(k\) 项时直接将维护的多项式除以 \(x\) 的 \(k\) 次幂，得到的多项式中新增了 \(k\) 项无意义的高次项系数，也可以选择直接删去这 \(k\) 项系数。
我们将说明得到的 \(\bar F_\text{root}(x)\) 的前 \(\sum_{i=1}^n s_i\) 项未删去项均有意义。
我们需要保证 \(F_n(x)\) 次数小于 \(c_n\) 的项系数为 \(0\)。设 \(z(n)\) 表示 \(\bar F_n(x)\) 已被删去的项数，易见 \(z(n)=\max\left\{c_n,\sum_{i\in \text{son}_n}z(i)\right\}\)。将 \(F_n\) 处理为 \(\bar F_n\) 时，我们会删去 \(z'(n)=z(n)-\sum_{i\in\text{son}_n}z(i)\) 项。
考察 \(\bar F_n(x)\) 有意义的项数 \(y(n)\)，易见 \(y(n)=\min_{i\in\text{son}_n}\{y(i),L\}-z'(n)\)。
我们想要证明 \(y(n)\geq L-\max_{i\in\text{subtree}_n}\{c_i\}\)。
采用归纳法，设上式对 \(n\) 的所有子结点 \(i\) 成立。
由 \(y(n)\) 的定义，有：\(y(n)\geq L-\max_{i\in\text{subtree}_n,i\neq n}\{c_i\}-z'(n)\)。
- 当 \(z'(n)=0\) 时，即有上式成立。
- 当 \(z'(n)\neq 0\) 时，注意到有 \(z(k)\geq \max_{i\in\text{subtree}_k}\{c_i\}\) 对任意 \(k\) 成立，并且 \(z'(n)=c_n-\sum_{i\in\text{son}_n}z(i)\leq c_n-\sum_{k\in\text{son}_n} \max_{i \in\text{subtree}_k}\{c_i\}\leq c_n-\max_{i\in\text{subtree}_n,i\neq n} \{c_i\}\) 成立，可知 \(c_n>\sum_{i\in\text{son}_n}z(i)\geq\max_{i\in\text{subtree}_n,i\neq n} \{c_i\}\)，因此 \(c_n=\max_{i\in\text{subtree}_n}\{c_i\}\)。于是 \(y(n)\geq L-c_n=L-\max_{i\in\text{subtree}_n}\{c_i\}\) 成立。
因此对于根结点有 \(y(\text{root})\geq L-\max_{i=1}^n\{c_i\}=\sum_{i=1}^n s_i\)。
即得到的 \(\bar F_\text{root}(x)\) 前 \(\sum_{i=1}^n s_i\) 项未删去项均有意义。
总时间复杂度 \(O(650^2(n+q\log w))\)。
所以为什么搞这么麻烦呢？因为不会多项式也不会 Berlekamp-Massey 算法啊！
B¶
solved by YZW&TYB
题意¶
随机生成一个数列，每次生成一个数，每个数都是\([1,n]\)范围内的整数，每次有\(p_i\)的概率生成\(i\)，当这次的数小于上次的数时结束，设此时共有\(x\)个数，求\(x^2\)的期望。
\(n\le 100\)
题解¶
根据期望DP的套路，我们选择倒推（不正推的具体原因大概是一些概率并不好算，比如在这题中，当前数列结尾为\(i\)的概率并不好算）。由期望的线性性，\(E[(x+1)^2]=E[x^2+2x+1]=E[x^2]+2E[x]+1\)，我们维护\(f_i\)和\(g_i\)，分别表示以\(i\)开头，不包括最后一个数，长度平方的期望和长度的期望。则容易写出转移方程：
有自己转移到自己的情况，但是转移关系不会成环，所以不需要高斯消元，只需要移项除一下就好了，最后把最后一个数的贡献加上即可。
时间复杂度\(O(n^2)\)。
C¶
solved by JLK&TYB
题意¶
给出\(a,b,c,n\)，构造三个长度为\(n\)的字符串\(s_1,s_2,s_3\)，满足\(lcs(s_1,s_2)=a,lcs(s_2,s_3)=b,lcs(s_1,s_3)=c\)。\(lcs\)表示最长公共子序列。
\(a,b,c,n\le 1000\)
题解¶
不妨假设\(a\le b\le c\)，那么可以：三个串的\([1,a]\)填一种，第二和第三个串的\([a+1,b]\)填一种，第三个串的\([b+1,b+c-a]\)和第一个串的\([b+1,b+c-a]\)填一种，剩下的位置填其它字符，使得\(lcs\)不会再增加。
D¶
upsolved by TYB
题意¶
给一棵\(n\)个节点的树，删\(k\)条边后再加\(k\)条边使得它还是一棵树，求方案数。
\(n\le 5\times10^4,k\le\min(100,n-1)\)
题解¶
考虑删掉\(k\)条边后，重新把它们连成树的方案数为：\(n^{k-2}\Pi_{i=1}^{k+1}size_i\)。推导过程见prufer序列学习笔记。
所以只需要考虑后面一坨怎么算。
考虑其意义，相当于把原树分成\(k+1\)个连通块后，从每个连通块选出一个点的方案数。树形DP，\(f_{i,j,0/1}\)表示以\(i\)为根的子树，分成\(j\)个连通块，\(i\)所在连通块是否选点的方案数。这是一个经典的树形背包问题，注意加上\(size\)和\(k\)的限制后其复杂度是\(O(nk)\)而不是\(O(nk^2)\)。
E¶
solved by JLK
题意¶
有一棵\(n\)个点的树，每个点有权值\(w_i\)。现在只给出每个点的权值区间\([l_i,r_i]\)，以及每条边两端的点权异或和，求有多少种赋值方案。
\(1 \le n \le 10^5,0 \le l_i \le r_i \lt 2^{30},0 \le w_u \oplus w_v \lt 2^{30}\)
题解¶
首先可以固定1为根，然后得到每个点\(x\)到根路径的异或和\(S_x\)，就可以得到每个\(w_1\oplus S_x\)的范围。由于是异或，可以按位考虑。先处理\(w_1 \oplus S_x \le R\)的情况。从大到小考虑，如果有一位\(R\)是0，那么\(w_1 \oplus S_x\)也必须是0。否则，\(w_1\oplus S_x\)这一位为0的情况全部都合法，为1的情况则需要看下一位。
这样就把限制条件转化为最多30个不相交的区间。
那么大于的情况可以看做是上面的区间挖掉\(w_1 \oplus S_x \le L-1\)的区间。可以给前者一个1的权值，后者一个-1的权值来判断。因为后者一定是前者的子集。如果覆盖某个数权值和为\(n\)，说明满足全部\(n\)个限制条件，这个数就可以被记入答案。
直接把所有区间拉出来排序然后记录就可以通过。不过考虑到每个区间实际上对应着Trie树上的一个点，只需要对Trie树动态开点，对每个区间打标记，最后遍历一次统计即可。具体就是能够往下走的时候就往下走，记入统计的点必须至少有一个儿子为空，否则不能保证一定合法（因为子树内可能有-1的权值）。
\(O(nlogw)\)
F¶
solved by JLK
题意¶
给定一个\(n\)个点\(m\)条边的无向图，两人博弈，每次可以删掉一条边或者删掉一个没有环的连通块。不能操作者输。问谁赢。
\(1 \le n \le 100,0 \le m \le \min\{200,n(n-1)/2\}\)
题解¶
删掉一条边，边数-1。
删掉一棵树，点数-k，边数-(k-1)，每次操作使点数+边数的奇偶性变化。
故只需判断n+m的奇偶性，奇数先手赢，偶数后手赢。
G¶
solved by JLK&TYB
题意¶
给定\(n,k,D\)，求\(a_i\ge 0,\sum\limits_{i=1}^na_i=D\)条件下\(\frac{D!}{\prod_{i=1}^n(a_i+k)!}\)。
\(1 \le n \le 50,0 \le k \le 50,0 \le D \le 10^8\)
题解¶
\(\frac{D!}{\prod_{i=1}^n(a_i+k)!}\)
\(=\frac{(D+nk)!}{\prod_{i=1}^n(a_i+k)!}\frac{D!}{(D+nk)!}\)
注意到\(\sum_{b_i\ge0,\sum\limits_{i=1}^n b_i=P}\frac{P!}{\prod_{i=1}^nb_i!}=n^P\)（可以考虑组合意义）
那么令\(b_i=a_i+k,P=D+nk\)，只需求出\(b_i\ge k\)的方案即可。
这可以用容斥解决。
递推出\(d_{i,j}\)表示有\(i\)个数小于\(k\)，且他们的和为\(j\)的方案数（内部有排序）。
那么答案就是\(\sum\limits_{i=0}^n (-1)^i\sum\limits_{j=0}^{i(k-1)}d_{i,j}C_n^iC_{D+nk}^j(n-i)^{D+nk-j}\)
\(D\)很大，但是\(nk\)很小，可以预处理出需要的数字。
\(O(n^2K)\)
H¶
upsolved by JLK
题意¶
定义运算\(\otimes \(，令\)p_i\)为第\(i\)个质数，若\(x=\prod_i p_i^{a_i},y=\prod_i p_i^{a_i}\)，则\(x \otimes y=\prod_i p_i^{|a_i-b_i|}\)。
\(b_i=\sum_{1 \le j,k \le n,j \otimes k =i}a_jk^c\)，求\(b\)。
\(1 \le n \le 10^6,0 \le a_i \lt 998244353,0 \le c \le 10^9\)
题解¶
不难发现\(x\otimes y=\frac{lcm(x,y)}{gcd(x,y)}=\frac{xy}{gcd(x,y)^2}\)
提取出gcd，\(b_i=\sum\limits_{d=1}^i\sum\limits_{x=1}^{n/d}\sum\limits_{y=1}^{n/d}[gcd(x,y)=1,xy=i]a_{dx}(dy)^c\)
注意到枚举\(x,y,xy\le n\)的复杂度是\(O(nlogn)\)的，可以对上式调换顺序。
\(b_i=\sum\limits_{x=1}^{i}\sum\limits_{y=1}^{i}[gcd(x,y)=1,xy=i]y^c\sum\limits_{d=1}^{\min\{\lfloor \frac nx\rfloor,\lfloor \frac ny\rfloor\}}a_{dx}d^c\)
令\(f_{x,i}=\sum\limits_{d=1}^ia_{dx}d^c(i \le \lfloor \frac nx\rfloor)\)，这个也可以\(O(nlogn)\)求出。
那么\(b_i=\sum\limits_{x=1}^{i}\sum\limits_{y=1}^{i}[gcd(x,y)=1,xy=i]y^c f_{x,\min\{\lfloor \frac nx\rfloor,\lfloor \frac ny\rfloor\}}\)
只需枚举\(x,y\)，计算每个\(b_i\)即可。
\(O(nlogn)\)（还要带上求gcd的复杂度？）
I¶
solved by JLK&TYB
题意¶
给一个长度\(n\)的排列，每个数可以不变或+1，求改变后的最小逆序对数。
\(1 \le n \le 2\times 10^5\)
题解¶
逆序对减少的唯一情况是\(i\)在\(i+1\)之后，然后\(i\)变成\(i+1\)，\(i+1\)不变。
那么只需要从小到大考虑，碰到满足条件的就变，然后固定后一位继续往后找。
如果从小到大枚举，当前能变却不变，一定是不优的。
以及开始需要算好一次总逆序对。
\(O(nlogn)\)
J¶
solved by YZW
题意¶
有数列 \(a_{1\dots n}\)，\(b_{1\dots m}\)，矩阵 \(W\) 通过 \(a,b\) 生成，具体地有 \(W_{i,j}=a_i+b_j\)。
求具有最大平均值的 \(W\) 子矩阵，并且至少为 \(x\) 行 \(y\) 列。
\(1\leq n,m\leq 10^5\)，\(1\leq x\leq n\)，\(1\leq y\leq m\)，\(0\leq a_i,b_i\leq 10^5\)。
题解¶
易见平均值为对应 \(a,b\) 子序列的平均值之和。
问题变为求序列中至少连续 \(x\) 个元素的最大平均值。考虑二分平均值 \(v\)，令 \(a'_i=a_i-v\)，即要求 \(\sum_{i} a'_i\geq 0\)，求前缀和，判断是否存在满足长度限制的差值为正即可。
\(O(n \log a_i+m\log b_i)\)
记录¶
开局分别看FIJ，出了一点问题，45min后都过了。
然后TYB写C，WA一次后发现相同处理有问题，JLK改对了(1:18)。
JLK先开B，但是发现推错了，于是TYB和YZW推式子，JLK写E。
E WA+RE后AC(2:35)。
然后YZW过B(2:43)。
YZW写H，JLK和TYB看G，推了一会式子后G过了(3:34)。
YZW说题读错了，然后一起卡DH至结束。
总结¶
JLK：数学题太多了，没有数理基础，需要补一补。这场罚时也有点多，比较简单的题还是需要谨慎一点。
Dirt¶
C(-1)
E(-2)
F(-1)
G(-1)
J(-1)