考虑求出所有 MST 的权值和再除以方案数, 方案数显然是 2mn.
按位考虑, 显然应该让 MST 里的边高位尽量为 0. 那么根据最高位是 0 还是 1 将点集划分成两部分, 整张图的 MST 就是由两部分各自的 MST 之间连一条最小边得到的. 两部分的 MST 权值和可以 dp 得到, 即设 f[i][j] 表示 i 个点权值在 0~2j-1 的 MST 权值和, 枚举最高位是 0 的点的数量 k, 由 f[k][j-1] 和 f[i-k][j-1] 转移而来. 问题只剩下求最小边的权值和.
这个东西也不是很好求, 考虑求最小边不小于某值的方案数. 同样根据最高位是 0 还是 1 划分点集成四个部分, 转移比较显然, 主要注意边界, 即所有边该位都为 1 的情况, 以及某边没有点的情况. 盯着这个边界调了一下午最后发现果然这里根本就没写挂, 而是预处理 2k 时少了一部分. 惨绝人寰.
复杂度 O(n4m2m), 虽然 darkbzoj 上只跑了 3s,bzoj 上还是根本卡不过去.
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- #define ll long long
- #define N 51
- #define M 8
- #define P 258280327
- char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
- int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
- int read()
- {
- int x=0,f=1;char c=getchar();
- while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
- while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
- return x*f;
- }
- int n,m,C[N][N],f[N][M+1],g[N][N][M],h[N][N][M][1<<M],p[N*M];
- void inc(int &x,int y){x+=y;if (x>=P) x-=P;}
- int inv(int a)
- {
- int s=1;
- for (int k=P-2;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;
- return s;
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("bzoj4770.in","r",stdin);
- freopen("bzoj4770.out","w",stdout);
- const char LL[]="%I64d\n";
- #else
- const char LL[]="%lld\n";
- #endif
- n=read(),m=read();
- C[0][0]=1;
- for (int i=1;i<=n;i++)
- {
- C[i][0]=C[i][i]=1;
- for (int j=1;j<i;j++)
- C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
- }
- p[0]=1;for (int i=1;i<(n+1)*m;i++) p[i]=(p[i-1]<<1)%P;
- for (int i=0;i<=n;i++)
- for (int j=0;j<=n-i&&j<=i;j++)
- h[i][j][0][0]=1;
- for (int k=1;k<m;k++)
- for (int x=0;x<(1<<k);x++)
- {
- for (int i=0;i<=n;i++) h[i][0][k][x]=p[i*k];
- for (int i=1;i<=n;i++)
- for (int j=1;j<=n-i&&j<=i;j++)
- for (int u=0;u<=i;u++)
- for (int v=0;v<=j;v++)
- if (u==0&&j==v||i==u&&v==0) inc(h[i][j][k][x],1ll*h[max(u,j-v)][min(u,j-v)][k-1][max(x-(1<<k-1),0)]*h[max(i-u,v)][min(i-u,v)][k-1][max(x-(1<<k-1),0)]%P);
- else inc(h[i][j][k][x],1ll*C[i][u]*C[j][v]%P*h[max(u,v)][min(u,v)][k-1][x]%P*h[max(i-u,j-v)][min(i-u,j-v)][k-1][x]%P);
- }
- for (int i=1;i<=n;i++)
- for (int j=1;j<=n-i&&j<=i;j++)
- for (int k=1;k<m;k++)
- for (int x=1;x<(1<<k);x++)
- inc(g[i][j][k],h[i][j][k][x]);
- for (int k=1;k<=m;k++)
- for (int i=1;i<=n;i++)
- {
- inc(f[i][k],f[i][k-1]);inc(f[i][k],f[i][k-1]);
- for (int j=1;j<i;j++)
- inc(f[i][k],1ll*C[i][j]*(1ll*f[j][k-1]*p[(i-j)*(k-1)]%P+1ll*f[i-j][k-1]*p[j*(k-1)]%P+p[(k-1)*(i+1)]+g[max(j,i-j)][min(j,i-j)][k-1])%P);
- }
- cout<<1ll*f[n][m]*inv(p[m*n])%P;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2851991.html