Nemlit

编辑于 2020-11-13 22:42

+ 关注

【题解】牛客挑战赛45 精

比赛中途因为一些问题更正了题面，再次为带来的麻烦道歉。非常抱歉。

然后 C 题的赛时问题可以查看 C 的题解了解，实在是非常抱歉。不好意思。

B - solution

对于树，当前点为根的子树内点权和不为 $k$ 的倍数时选择当前点连向其父亲的边，否则不选择这条边。

C - solution

枚举操作的区间的长度，对应求出 $z$ 的最大值，然后从高位向低位贪心求代价。

复杂度 $\mathcal O(n\log w)$

非常抱歉这道题糟糕的题面为您带来了糟糕的比赛体验，数据的问题在于出题人的题面写的读入规则是 $n,A_1,d,k,y$ ，但实际上出题人的代码读入顺序为 $n,d,A_1,k,y$ ，也就是说我们的题面写反了/lb
但是小样例满足无论 $A_1,d$ 读反答案都是一样的，所以我们误以为是选手提交有问题。实在是抱歉。
然后本次比赛的题面存在许多细节都存在描述不严谨以及错误等问题，非常抱歉为您带来了如此糟糕的比赛体验，也与我们在比赛前没有对题目进行仔细的检查有关。

D - solution

由于 $T_2$ 以及每次修改是随机生成的，所以我们每次修改之后暴力遍历整个子树修改对应点的深度的期望次数是 $m\log n$ （注意到单次复杂度的期望为 $\frac{1}{n}\sum sz_i=\frac{1}{n}\sum dep(i)=\log n$ ）

我们考虑对于 $T_1$ 上的每个点下面再挂一个点，边权为在 $T_2$ 中的深度。此时两点的距离即为两个节点新挂的节点的距离。由于边权非负，所以我们等价于维护新树上的直径。

每次修改操作，我们可以将 $T_2$ 子树中的每个点依次修改（即暴力）然后动态维护直径即可，标算在实现上采取的是 $\mathcal O(n\log n)\sim \mathcal O(1)$ 的 LCA，所以复杂度为 $\mathcal O((n+m)\log n)$ ，但范围只开了 $10^5$ ，所以 $\log^2$ 的做法也可以通过本题。

动态维护直径：

如果当前修改的这个点是修改前树的直径上的一个端点，那么另一个端点一定是新的直径上的一个端点，比较一下即可。
如果当前修改的点不是修改前树的直径的一个端点，那么原来树的直径上的端点至少有一个是新的树的直径的端点，也比较一下即可。

E - solution

先考虑 $m=n-1$ 的情况，令 $d_i$ 表示节点 $i$ 的度数。

删除一个点，对于联通块数量的影响为： $d_i-1$ ，然后与他相连的点的度数都 $-1$ 。也就是如果一条边连接的两个点同时被选择，就有 $-1$ 的贡献。

每个点被选中的概率均为 $\frac{k}{n}$ ，所以点权的期望贡献即 $\sum d_i\times \frac{k}{n}=2m\times \dfrac{k}{n}$ 。再考虑边，一条边的两个端点被同时选中的概率为 $\frac{\binom{n-2}{k-2}}{\binom{n}{k}}$ ，所以边的贡献为： $-m\times\frac{\binom{n-2}{k-2}}{\binom{n}{k}}$ 。

所以对于一棵树，答案为： $1-k+2m\times \dfrac{k}{n}-m\times \dfrac{\binom{n-2}{k-2}}{\binom{n}{k}}$

对于仙人掌，所以如果一个点的度数为 $d_i$ ，且其处于环上，那么删除其对于联通块数量的影响为： $d_i-2$ ；否则为： $d_i-1$ ，并且这个环会被破坏掉

发现每个环也只有第一次被选中的时候有影响，且彼此对于答案的贡献的期望也是独立的！

不考虑环的贡献的计算方式显然和树的计算方式一样。对于一个大小为 $S$ 的环被选中的概率为： $1-\dfrac{\binom{n-|S|}{k}}{\binom{n}{k}}$ 。由于环的贡献是负数，所以我们只需要最大化： $\sum\binom{n-|S|}{k}$ 即可。

注意到，环的数量固定是 $n-m+1$ 的，对于大小 $>3$ 的环对于答案的贡献显然没有大小为 $3$ 的环对于答案的贡献优。同时，如果我们能够构造一个大小 $>3$ 的环，那么就一定可以构造一个大小为 $3$ 的环然后挂一条链。

所以我们构造的方案一定是由很多个大小为 $3$ 的环构成的仙人掌图，一种可行的方案是形如：

于是最后的答案其实就是：

$1-k+2m\times \dfrac{k}{n}-m\times \dfrac{\binom{n-2}{k-2}}{\binom{n}{k}}-(m-n+1)(1-\dfrac{\binom{n-3}{k}}{\binom{n}{k}})$

把组合数拆开化简一下就可以得到：

$n-m-k+2m\times \dfrac{k}{n}-m\times \dfrac{k(k-1)}{n(n-1)}+(m-n+1)\times \dfrac{(n-k)(n-k-1)(n-k-2)}{n(n-1)(n-2)}$

F - solution

定义 $f(G,t)$ 表示对于图 $G$ 其最小生成树的最大边权小于等于 $t$ 的情况下的 MST 的边权和的期望。

定义 $F(G,t)$ 表示对于图 $G$ 其最小生成树的最大边权小于等于 $t$ 的情况下其 MST 的边权和的平方的期望。

可以明确的一点为， $f(G,t)$ 与 $F(G,t)$ 均为关于 $t$ 的多项式，于是只需要代入 $t=1$ 即可得到答案。

为了进行转移，我们额外定义 $p(G,t)$ 表示图 $G$ 的最小生成树的最大边权小于等于 $t$ 的概率，这也是一个关于 $t$ 的多项式。

考虑计算 $f(G,t)$ ，我们枚举这张图 $G$ 上的 MST 的边权最大的边 $(u,v)$ ，这条边应该将图分成两个集合，不妨直接枚举这两个集合 $S,T$ （注意 $S,T$ 应该为无序集合），那么此时有：

$f(G,t)=\int_0^t dx\cdot (f(S,x)p(T,x)+f(T,x)p(S,x)+p(S,x)p(T,x)x)\cdot (1-x)^{|S\to T|-1}(|S|\to |T|)$

后者的意义为对于集合 $S$ 和集合 $T$ 枚举一条边连接两者且权值大于两者的和，这条边对答案的贡献为 $x$ ，同时连接 $S\to T$ 中的其他边的边权均大于这条边。

考虑计算 $F(G,t)$ ，我们类似处理，这里根据 $(a+b)^2=a^2+b^2+2ab$ ，不难得到转移：

这里两张图的贡献合并需要注意顺序，实际上我们在计算 $(a+b+c)^2$ ，但是可以逐个合并答案。

先合并 $F(S,x)$ 和 $x$ 的答案有：

$(F(S,x)+2f(S,x)x+x^2p(S,x))$

这是一个新的平方项，此时考虑维护一次项即 $f(S,x)+xp(S,x)$

然后和 $F(T,x)$ 合并即可。（方便表述设 $u$ 为一次项， $u^2$ 为二次项）

$\int_0^x \bigg(u^2\cdot p(T,x)+2u\cdot f(T,x)+F(T,x)p(S,x)\bigg)\cdot (1-x)^{|S\to T|-1}(|S|\to |T|)$

考虑 $p(G,t)$ ，类似的，我们枚举 MST 上最大的边权，同时枚举它将集合分成的两个子集，这两个子***附带一个概率，不难得到转移：

$p(G,t)=\int_0^t dx\cdot (p(S,x)p(T,x))(1-x)^{|S\to T|-1}(|S\to T|)$

稍微归纳一下，不难发现 $p(G,t)$ 为关于 $t$ 不超过 $2|G|$ 级别的次幂多项式。其中，边界条件为 $|G|$ 中只有一个节点，此时 $p(G,t)=1$ ，同理于 $f(G,t),F(G,t)$

对于两类转移，不妨先求出后者关于 $x$ 的多项式，然后通过积分表示成关于 $t$ 的多项式，然后求和即可，不难观察出最高次幂不超过边数乘以 $2$ ，复杂度为 $\mathcal O(3^n\cdot m^2)$

实际上这个多项式可能是 $n+m$ 级的？不太清楚，反正上界是 $2m$ 就对了。

算一下感觉这个玩意儿非常不能过，实际上存在严格 $\mathcal O(3^n\cdot m+m^2\cdot 2^n)$ 的做法（预处理多项式的点值就可以了）然而在 $n<15$ 的情况下这个做法的速度都几乎被 $\mathcal O(3^n\cdot m^2)$ 吊打，因为对于更小的状态多项式的次幂更低...最后测出来 $n=12$ 的情况下的极限数据，只需要运行 $2.5\cdot 10^8$ 次。（ $n=14$ 的时候运行速度好像差不多？）

如果你写了 $\mathcal O(3^n\cdot m+2^n\cdot m^2\sim 2^n\cdot m\log m)$ 的做法大概也是可以通过的，需要略注意常数。（所以我把时限开成了 4s）

如果写 $\mathcal O(m^2\cdot 3^n)$ 的算法大概是没啥问题的。

ps：这个做法可能可以拓展到更大的次幂，但是转移时计算量的增长倒是挺快的，出题人没有耐心算了，就单独拿了平方出题了。

G - solution

根据裴蜀定理，条件等价于 $\gcd(a_i[i\in S],P)|x$ ，将所有数先和 $P$ 取 $\gcd$ ，对 $P$ 进行质因数分解，对于某个 $p$ ，假设 $a_i$ 在对应次幂上不高于 $x$ 则标记为 $1$ ，否则为 $0$ ，这样每个 $a_i$ 可以对应成一个二进制数 $a_i'$ 。

于是对于 $k=1$ 的时候集合有贡献等价于 $a_i'$ 按位或的结果为全集 $U$ ，接着考虑 $k\ne 1$ 的情况。

记 $g(T,k)$ 表示集合 $T$ 对当前 $k$ 的贡献次数，那么不难得到 $g(T,k)=\sum_{T\subseteq S} g(S,k-1)$ ，不难通过归纳法证明一个大小为 $|S|$ 的集合 $S$ 对答案的贡献为 $k^{n-|S|}$ 。（二项式定理展开即可证明）

这样对每个位置选/不选列一个集合幂级数，定义运算为 $FWT_{or}$ ，那么可以得到答案为 $k^n\times \prod (1+ \frac{1}{k}x^{a_i'})[x^{U}]$ ， $U$ 为全集。

注意到点值只能为 $1$ 或 $\frac{1}{k}+1$ ，计算有多少个 $1+\frac{1}{k}$ 可以通过将所有 $a_i'$ 加起来得到的集合幂级数 $F(x)$ 做 FWT 得到，计算快速幂，然后 IFWT 还原即可，复杂度为 $\mathcal O(T\times (n\log P+2^{\omega(P)}(\omega(P)+\log n)))$ ，其中 $\omega(P)$ 表示 $P$ 的质因子个数，本题中为 $15$ ，需要略注意常数。