bzoj4770 图样

题意

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<cstdio>

#include<iostream>

#include<algorithm>

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<sz;++i)a[i]=0;

  }

  int res(){

    int ans=0;

    for(int i=0;i<sz;++i){

      ans=(ans+a[i]*1ll*i%mod)%mod;

    }

    return ans;

  }

}F[55][55][8];

bool vis[55][55][8];

calc solve2(int n1,int n2,int m){

  if(vis[n1][n2][m])return F[n1][n2][m];

  calc& tmp=F[n1][n2][m];tmp=calc(1<<m);

  if(m==1){

    tmp[1]=2;tmp[0]=(qpow(2,(n1+n2))+mod-2)%mod;

    return tmp;

  }

  vis[n1][n2][m]=true;

  calc tmp1(1<<m),tmp2(1<<m);

  tmp1=solve2(n1,n2,m-1);

  for(int i=0;i<tmp1.sz;++i){

    tmp[i]=(tmp[i]+tmp1[i]*2%mod)%mod;

    tmp[tmp1.sz+i]=(tmp[tmp1.sz+i]+tmp1[i]*2%mod)%mod;

  }

  for(int i=1;i<n1;++i){

    tmp1=solve2(i,n2,m-1);

    for(int j=0;j<tmp1.sz;++j){

      tmp[j]=(tmp[j]+tmp1[j]*1ll*C[n1][i]%mod*2%mod*qpow(2,(n1-i)*(m-1))%mod)%mod;

    }

  }

  for(int i=1;i<n2;++i){

    tmp1=solve2(n1,i,m-1);

    for(int j=0;j<tmp1.sz;++j){

      tmp[j]=(tmp[j]+tmp1[j]*1ll*C[n2][i]%mod*2%mod*qpow(2,(n2-i)*(m-1))%mod)%mod;

    }

  }

  for(int i=1;i<n1;++i){

    for(int j=1;j<n2;++j){

      tmp1=solve2(i,j,m-1);tmp2=solve2(n1-i,n2-j,m-1);

      for(int k1=0;k1<tmp1.sz;++k1){

	for(int k2=0;k2<tmp1.sz;++k2){

	  tmp[min(k1,k2)]=(tmp[min(k1,k2)]+tmp1[k1]*1ll*tmp2[k2]%mod*C[n1][i]%mod*C[n2][j])%mod;

	}

      }

    }

  }

  //  printf("%d %d %d\n",n1,n2,m);

  //  for(int i=0;i<(1<<m);++i)printf("%d ",tmp[i]);printf("\n");

  return tmp;

}

int SOLVE2(int n1,int n2,int m){

  if(vis[n1][n2][m])return F[n1][n2][m].res();

  else solve2(n1,n2,m);

  return F[n1][n2][m].res();

}

bool used[55][55];int f[55][55];

int solve(int n,int m){

  if(used[n][m])return f[n][m];

  if(n==1){

    used[n][m]=true;return f[n][m]=0;

  }

  if(m==1){

    used[n][m]=true;

    return f[n][m]=(qpow(2,n)-2+mod)%mod;

  }

  used[n][m]=true;

  int &ans=f[n][m];

  ans=2ll*solve(n,m-1);

  for(int i=1;i<n;++i){

    ans=(ans+C[n][i]*1ll*(qpow(2,(n-i)*(m-1))*1ll*solve(i,m-1)%mod+qpow(2,i*(m-1))*1ll*solve(n-i,m-1)%mod+qpow(2,n*(m-1))*1ll*(1<<m-1)%mod+SOLVE2(i,n-i,m-1))%mod)%mod;

  }

  return ans;

}

int main(){

  C[0][0]=1;

  for(int i=1;i<55;++i){

    C[i][0]=1;

    for(int j=1;j<=i;++j){

      C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;

    }

  }

  int n,m;

  scanf("%d%d",&n,&m);

  printf("%lld\n",qpow(qpow(2,n*m),mod-2)*1ll*solve(n,m)%mod);

  return 0;

}

巴特西

bzoj4770 图样

题意

分析

最新文章

热门文章