SRM672 div1 题解

Easy

题目大意：

给定一个无穷长的数列，一开始有$a_i=i$。从$i\geq{2}$开始，对于所有$i|j$且$j>i$的$j$进行操作$swap(a_j,a_{j+1})$。

问经过充分长的时间后$a_n$的值。

数据范围$n\leq{10^{10}}$。

题解：

我只能YY出有效的操作次数不是非常多，并且答案波动的范围非常小。

于是写了一个记忆化的因子分解。

然后暴力进行操作。

时间复杂度玄学。

结果在$n=2$时挂掉了。

官方的解好像就是这样的，但是看别人的代码好像还有别的姿势？

Medium

题目大意：

求有多少张点数为$n$的无向图使得至多添加一条边之后存在一条欧拉回路。

输出答案对$10^9+7$取模的余数。

数据范围$n\leq{2000}$。

题解：

首先要求的无向图肯定是连通的。

如果直接就是欧拉回路的话，需要满足所有点的度数都是偶数。

如果需要添加一条边的话，则是有且仅有两个点的度数是奇数。

假设我们已经能够求出$g_n$表示$n$的点的所有点的度数都是偶数的连通图的个数。

那么答案就是$g_{n}\times(\frac{n(n-1)}{2}+1)$。

因为我们可以枚举哪两个点的度数为奇数，如果这两个点之间没有边则连上一条边，否则删除两个点之间的边。

我们再令$f_{n}$表示$n$个点所有点的度数均为偶数的无向图的个数。

这个可以直接计算，我们单独拿出某个点，于是剩下的无向图的个数为$2^{\frac{(n-1)(n-2)}{2}}$，对于我们得到的每个无向图，显然都会有偶数个度数为奇数的点。那么独立的那个点必须向无向图中所有度数为奇数的点连边，这能够保证独立的点的度数也为偶数，且连边的方法是唯一的。

于是我们就得到了$f_{n}=2^{\frac{(n-1)(n-2)}{2}}$。

显然我们可以再利用补集转化求$g_n$，只需要减去不连通的所有点度数均为偶数的图个数就行了。

对于某个点，枚举这个点所在连通块的大小，递推式是这样的：

$g_{n}=f_{n}-\sum_{i=1}^{n-1}\binom{n-1}{i-1}g_{i}f_{n-i}$

时间复杂度$O(n^2)$。

hard

题目大意：

给定一个边带权的无向完全图，以$0$号点为根进行Prim算法求最大生成树，当边权相同时随便选一个点加入当前集合。

对于每一个点，你要求出这个点在Prim算法的所有可能情况中最早第几个被加入当前集合。

数据范围$n\leq{50}$，边权范围$0\leq{w}<10$。

题解：

考虑最终形成的最大生成树的形态。

我们可以考虑，先一并加入所有权值为$9$的边，再一并加入所有权值为$8$的边，。。。，依此类推。

那么我们这样想，假设我们要求的某个点$i$通过权值为$j$的边加入了集合，那么必然有所有权值$>j$的边对于连通性做出的贡献都已经被考虑过了。

不妨利用动态规划处理集合之间的合并：

对于每个根$i$，以及每个权值$j$，我们处理出只考虑$>j$的权值的$i$所在的最大连通块，大小为$cnt$。

那么对于这个连通块所有相邻点$k$，如果边权恰为$j$，点$k$就能在最多$cnt$个点之后加入$i$所在的集合。

我们可以新建一张有向图，连接$(i,k,cnt)$，于是这个问题转化为了一个图论中的最短路问题。

利用Folyd进行处理。

时间复杂度$O(wn^3)$。