存在两个串，\(0\)的个数或者\(1\)的个数均大于\(n\)。
在\(0\)或\(1\)间把另外一个字符插进去。
结论：对于\(n\)阶排列，合法的方案数为\(2^{n-1}\)。
证明：
对于\(n\)阶排列，假设第一个位置填的是\(x\)，那么前缀会是\(x,x-1,\ldots,1\)。
令\(f_i\)为\(i\)阶排列合法方案数，\(f_0=1\)，有递推式：
\(f_n=\sum\limits_{i=1}^n f_{n-i}=2^{n-1}\)。
第五发才过...菜死了，我的做法相对较复杂，谨慎观看。
令\(w=\bigoplus\limits_{(u,v)\in E}w_{u,v}\)。
结论：存在最优解，需要填的边，除一条边权为\(w\)外，其他均为\(0\)。
证明：
若有两条边权不为\(0\)，将其中一条改变这两的异或，\(\text{MST}\)不会增大。
先搜出补图连通性：\(\text{cf920e}\)。
将补图连通的点先缩起来，用给出的边跑一个\(\text{MST}\)，用到的边权是必须用到的。
如果存在补图的某个连通块，边数\(\ge\)点数，那么在树的基础上将\(w\)放在另一条边，那么\(\text{MST}\)就为之前得到的。
那么现在要考虑补图的某条边边权为\(w\)，对\(\text{MST}\)的影响。
对于原图但不在\(\text{MST}\)的边，考虑其是否可能加入\(\text{MST}\)，将其与\(w\)取\(\min\)，在加上原\(\text{MST}\)，就为真正的\(\text{MST}\)。
感觉讲得及其不清楚，就放下代码吧...
定义：点\(i\)简写为\(i\)，标签\(i\)简写为\(\hat{i}\)
观察1：对于\(a_i=i\)的点，若存在解，则一定存在没有操作过\(i\)的解。
证明：
若\(\hat{i}\)离开\(i\)，之后必定还要回到\(i\)，找到第一次离开\(i\)的操作与第一次回到\(i\)的操作，容易观察将这两次操作删除，不会对结果产生影响。
于是我们可以忽略所有\(a_i=i\)的所有点。
考虑如果一开始就是单轮换，该怎么做？
枚举任何一个点，作为中心，其他点与其连边。
这形成了一个菊花图，考虑中心的标签，将中心与上面标签数字的点交换，依次操作所有边后，显然合法。
但如果开始不是单轮换呢？
观察2：对于两个轮换，交换这两个轮换中任意两点的标签，会合并成一个轮换。
我们的大概思路是：将所有轮换合并成一个轮换，再将单轮换调整好。
我们依然枚举任意一个点，作为中心，对其他点极角排序，考虑相邻的两个点这种连边，即外围的蓝色边。
利用蓝色边，将多个轮换合并成一个轮换，这很容易实现。
但还有另外一种情况
如果选择的中心点在凸包上，是可能蓝色边与黄色边有交的。
考虑所有的点都在凸包上的情况。（否则选择不在凸包上的点，所有蓝色边有效）
但这样的蓝色边至多有一条，考虑是否可以忽略这条蓝边，以达到目的。
这相当于，对于一个凸包上的边，忽略两条相邻的边，是否可以通过其他边以达到目的，由于一个轮换至少有两个点，这是可行的。
综上，我们在\(O(n\log n)\)（极角排序），在最多\(1.5n\)次操作内解决了此问题。
待更
待更
Codeforces Round #715 (Div. 1)
原文：https://www.cnblogs.com/Grice/p/14670584.html
