A.异或排序

对于每相邻两个数，找到他们最高的值不同的位，根据具体的值可以知道S上该位的值是什么

判断下是否有矛盾即可

时间复杂度: O(n)

B.二进制翻转

枚举当前要计算的数的位数，考虑从左右往中间dp

f[i][j][k][cmp1][cmp2]表示考虑了前 i 位和后 i 位，前 i 位需要 j 个进位，后 i 位的进位为 k，前 i 位和后 i 位和上限的大小情况分别是 cmp1，cmp2

转移时，同时枚举第 i+1 位和倒数第 i+1 位的值，枚举该位最后是否是 1 ，根据这个判断是否需要进位即可

时间复杂度 O((logn)^2)

C.树的方差

根据方差的定义，可以发现V[x]=E[x^2]-(E[x])^2

其中显然E[x]=(2*n-2)/n，于是我们只需要算E[x^2]即可

根据prufer序列的定义，一个点的度数等于他在prufer序列中的出现次数+1

于是我们可以枚举一个点出现了几次，用简单的计数技巧计算即可

D.生成树计数

考虑一堆数的和的k次方，就是从这堆数里选k个数（可以重复），一个方案的权值是选的数的乘积，答案就是所有方案的权值之和

对于传统的生成数计数，我们可以用矩阵树定理解决

在这题里我们可以用多项式 \sum_{i=0}^{k}\frac{(wx)^i}{i!} 代替权值 w，然后构建基尔霍夫矩阵，求行列式

这样求出的行列式是一个 n*k 次的多项式，x^k 的系数乘上 k! 后就是答案

元素是多项式的矩阵行列式不是很好求，我们可以将x=0..n*k 带入多项式后求出行列式，然后用拉格朗日插值还原多项式

时间复杂度 O(n^4*k)