NOI.AC 31 MST——整数划分相关的图论(生成树、哈希)[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

模拟 kruscal 的建最小生成树的过程，我们应该把树边一条一条加进去；在加下一条之前先把权值在这一条到下一条的之间的那些边都连上。连的时候要保证图的连通性不变。

已经加了一些树边之后，图的连通性是怎样的呢？这可以是一个整数划分的问题。据说方案只有4万多，所以可以搜一下，搜出有 k 个连通块的方案数。

为了转移和转移时算方案数，还要记录每个方案的：各个连通块的点数，所有的空位(可放边)数。

可以用 map 来存状态。 map 的角标是一个随便哈希的值，map 的值是这个状态的编号，也是这个状态的其他信息在那些数组里的角标。这样要算下一个状态是谁的时候就可以通过记录的“各个连通块的点数”找到”下一个状态的各个连通块的点数“，再用一样的方法哈希起来，利用 map 就能找到下一个状态的编号了。

因为不太会写，所以就学习（抄）了一下别人的。

1.注意算排列时判 n<m ！数组越界本地可能答案正确，但交上去就会爆。

2.不知 1e4 是怎么确定的？

3.学题解 N=41 WA了最后两个点，改成45就A了。不知为何。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #define ull unsigned long long #define ll long long using namespace std; const int N=45,M=1e4,mod=1e9+7,base=M;//N=41会WA两个点？！ int n,a[N],cd[N],vec[N][M][N],edg[N][M];//N的情况里第M个的 空位/第N个连通块的点数 int dp[N][M],lm,tmp[N],id[N][N],tmpx[N],top; int jc[N*N],jcn[N*N]; ull hsh; map<ull,int> mp[N];//用值得到另一个角标(cd) int rdn() { int ret=0;bool fx=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-')fx=0; ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return fx?ret:-ret; } int pw(int x,int k) { int ret=1;while(k){ if(k&1ll)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=1ll;}return ret; } void init() { lm=(n*(n-1)>>1);//not n jc[0]=1; for(int i=1;i<=lm;i++) jc[i]=(ll)jc[i-1]*i%mod; jcn[lm]=pw(jc[lm],mod-2); for(int i=lm-1;i>=0;i--) jcn[i]=(ll)jcn[i+1]*(i+1)%mod; } void dfs(int sm,int cr,int lst) { if(lst*(lm-cr+1)>sm) return; if(cr>lm) { hsh=0; for(int i=1;i<cr;i++)hsh=hsh*base+tmp[i]; mp[lm][hsh]=++cd[lm]; for(int i=1;i<cr;i++) { vec[lm][cd[lm]][i]=tmp[i]; edg[lm][cd[lm]]+=(tmp[i]*(tmp[i]-1)>>1); } //printf("edg[%d][%d]=%d\n",lm,cd[lm],edg[lm][cd[lm]]); return; } if(cr==lm) { tmp[cr]=sm;dfs(0,cr+1,0);//有剪枝，所以一定不降 return; } for(int i=lst;i<=sm;i++) { tmp[cr]=i; dfs(sm-i,cr+1,i); } } int P(int n,int m) { if(n<m) return 0;//!!!!!! //printf("jc[%d]=%d jcn[%d]=%d\n",n,jc[n],n-m,jcn[n-m]); return (ll)jc[n]*jcn[n-m]%mod; } int main() { n=rdn(); init(); for(int i=n;i>1;i--) a[i]=rdn(); a[1]=(n*(n-1)>>1); for(int i=1;i<=n;i++) lm=i,dfs(n,1,1); dp[n][1]=1; for(int i=n;i>1;i--) for(int s=1;s<=cd[i];s++) { //printf("y dp[%d][%d]=%d\n",i,s,dp[i][s]); //printf("%d-%d=%d %d-%d-1=%d\n",edg[i][s],a[i+1],edg[i][s]-a[i+1],a[i],a[i+1],a[i]-a[i+1]-1); dp[i][s]=(ll)dp[i][s]*P(edg[i][s]-a[i+1],a[i]-a[i+1]-1)%mod; //printf("now dp[%d][%d]=%d(P=%d)\n",i,s,dp[i][s],P(edg[i][s]-a[i+1],a[i]-a[i+1]-1)); memset(id,0,sizeof id); for(int j=1;j<=i;j++)tmp[j]=vec[i][s][j]; for(int u=1;u<=i;u++) for(int v=u+1;v<=i;v++)//哪两个集合  { //printf("i=%d s=%d tmp[%d]=%d tmp[%d]=%d\n",i,s,u,tmp[u],v,tmp[v]); if(!id[tmp[u]][tmp[v]]) { top=0; for(int p=1;p<=i;p++) if(p!=u&&p!=v)tmpx[++top]=tmp[p]; tmpx[++top]=tmp[u]+tmp[v]; for(int p=top-1;p;p--)//插排 if(tmpx[p]>tmpx[p+1])swap(tmpx[p],tmpx[p+1]); else break;//else hsh=0; for(int p=1;p<=top;p++) hsh=hsh*base+tmpx[p]; id[tmp[u]][tmp[v]]=mp[i-1][hsh]; //printf("id[%d][%d]=%d\n",tmp[u],tmp[v],id[tmp[u]][tmp[v]]);  } dp[i-1][id[tmp[u]][tmp[v]]]= (dp[i-1][id[tmp[u]][tmp[v]]]+(ll)dp[i][s]*tmp[u]*tmp[v])%mod; //printf("dp[%d][%d]=%d(dp=%d tmu=%d tmv=%d)\n",i-1,id[tmp[u]][tmp[v]],dp[i-1][id[tmp[u]][tmp[v]]],dp[i][s],tmp[u],tmp[v]);  } } //printf("%d-%d=%d %d-%d-1=%d\n",edg[1][1],a[2],edg[1][1]-a[2],a[1],a[2],a[1]-a[2]-1); dp[1][1]=(ll)dp[1][1]*P(edg[1][1]-a[2],a[1]-a[2]-1)%mod; printf("%d\n",dp[1][1]); return 0; }