hihoCoder Challenge 28 题解

6
2

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)

  • 厉害了。。。为什么这么厉害

  • A题的数据,貌似弄得不加判断是否矛盾也能AC

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享