ABC386 VP总结

比赛链接

Result

E 题没开 LL 爽挂 3 发，F 题咋是压哨过的

Solution

F - Operate K

令 \(dp_{i,j}\) 为 \(S\) 的前 \(i\) 位和 \(T\) 的前 \(j\) 为的最小编辑距离，转移是显然的。因为 \(dp_{i,j}\) 只会从 \(dp_{i,j-1},dp_{i-1,j},dp_{i-1,j-1}\) 转移过来，我们可以用滚动数组解决空间问题

又因为编辑距离 \(k\le 20\)，我们可以只在 \([i-k,i+k]\) 中枚举 \(j\)，时间复杂度降为 \(O(nk)\)

code

G - Many MST

将边权转化到 \(0\sim m-1\)，最后答案加上 \((n-1)m^{\frac{n(n-1)}{2}}\) 即可。令 \(G_i\) 为边权 \(<i\) 组成的图，\(c(G_i)\) 为 \(G_i\) 的连通块个数，那么最小生成树边权和为 \(\sum\limits_{i=1}^{m}(c(G_i)-1)\)，通过枚举边权讨论容易证明

那么令 \(S\) 为 \(m^{\frac{n(n-1)}{2}}\) 个完全图的集合，\(C(G_k)\) 为 \(G_k\) 连通块的集合，那么答案为：

\[(n-1)m^{\frac{n(n-1)}{2}}+\sum\limits_{G\in S}\sum_{i=1}^{m}(c(G_i)-1) \]

化简得到：

\[(n-m-1)m^{\frac{n(n-1)}{2}}+\sum\limits_{i=1}^{m}\sum\limits_{G\in S}\sum\limits_{H\in C(G_i)}1 \]

对于每一个 \(i\)，我们尝试求 \(\sum\limits_{G\in S}\sum\limits_{H\in C(G_i)}1\)：

对于一个 \(v\) 点 \(e\) 边的图 \(H\)，我们考虑 \(G\) 中的所有边：

• 端点均不在 \(H\) 中，可以随便选，\(m^{\frac{(n-v)(n-v-1)}{2}}\) 种选法
• 有一个端点在 \(H\) 中，这条边一定不在 \(H\) 中，\((m-i)^{v(n-v)}\) 种选法
• 两个端点都在 \(H\) 中，\(e\) 条边在 \(0\sim k-1\)，剩下的边不在，\(i^{e}(m-i)^{\frac{v(v-1)}{2}-e}\)

乘起来即可。令 \(f(j)\) 为有 \(j\) 个节点的所有连通块 \(H\) 的 \(i^{e}(m-i)^{\frac{j(j-1)}{2}-e}\) 总和，答案化为：

\[(n-m-1)m^{\frac{n(n-1)}{2}}+\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{n}{n\choose j}f(j)(m-i)^{j(n-j)}m^{(n-j)(n-j-1)} \]

再考虑如何求出 \(f(j)\)，用总方案数减去不成为连通块的方案数。为了保证连通块外的点不连进来改变 \(j\)，需要先在里面确定一个点以去重，那么：

\[f(j)=m^{\frac{j(j-1)}{2}}-\sum_{k=1}^{j-1}{j-1\choose k-1}f(k)(m-i)^{k(j-k)}m^{\frac{(j-k)(j-k-1)}{2}} \]

直接把式子代进去算即可

code