题意

n个点的完全图,每个点的点权是在m位的二进制数中随机选取的.每条边的边权是两个点的点权的异或值.

问最小生成树的边权和的期望.模一个质数输出.

分析

• 考试的时候写这个题,然后期望得分100->实际得分20,然后调着调着没调出来呢,然后机房跳闸机器还原当时的打表程序没了.
  然后悲痛地按考试时的方法重写一遍,重新打表,能A啊... 我的80分呢?

怎样少挂题?提高1A率.怎样提高1A率?少挂题.

首先只有\(2^nm\)种情况,我们可以算出所有的最小生成树的权值之和再除以总的方案数.

对于某种点权确定的图,我们要最小化边权之和,首先可以考虑最小化最高位是1的边数.

如果所有点的最高位都是1或0,那么不会有最高位是1的边.

否则,我们总能做到只有一条边最高位是1.

可以先在最高位是1的所有点之间连边形成一个连通块,再在最高位是0的所有点之间连边形成一个连通块.然后在两个连通块之间连一条边.

按照这个思路可以定义solve(n,m)求出n个点,权值m位的所有的图的MST权值之和.

最高位全都相同的情况,直接递归到solve(n,m-1)

最高位不同的情况,分成两个连通块,枚举连通块大小i和(n-i),分别递归到solve(i,m-1)和solve(n-i,m-1)

此时还要考虑两个连通块之间连的边的边权的较低m-1位.

这个边权相当于一个连通块有i个随机的m-1位二进制数,另一个连通块有n-i个随机的m-1位二进制数,各选出一个使得异或值最小.

于是还要再定义一个DP求出所有方案中这个最小的异或值之和.

然后我写得复杂度比较高,只能打表...把比较暴力过不了的代码放上来.

#include
    
     #include
     
      #include
      
       using namespace std;const int mod=258280327;int C[55][55];int qpow(int a,int x){  int ans=1;  for(;x;x>>=1,a=a*1ll*a%mod){    if(x&1)ans=ans*1ll*a%mod;  }  return ans;}struct calc{  int a[256],sz;  int& operator [](int x){return a[x];}  calc(){}  calc(int x){    sz=x;for(int i=0;i