51Nod 1601 完全图的最小生成树计数

分析：

这是一张完全图，并且边的权值是由点的权值$xor$得到的，所以我们考虑贪心的思想，考虑$kruskal$的过程选取最小的边把两个连通块合并，所以我们可以模仿$kruskal$的过程，倒着做$kruskal$，设定当前的最高位为$d$，我们把点集分为两个集合，$s$集合代表$d$位为$1$的点，$t$集合代表$d$位为$0$的点，就是$st$两个连通块，考虑这两个连通块的连接，把$t$连通块建出一棵$trie$树，然后枚举$s$集合中的点，去查找最小边，然后统计最小边的数量，递归解决$st$两个连通块，最后统计方案数的时候就是乘法原理...

为什么按照每一位的$01$来划分集合？我们考虑现在把$s$拆成两个连通块，这样一共有三个连通块，如果按照贪心的思想，一定是先连接$s$的连通块，因为最高位一定是$0$，这样边比较小...

需要注意的细节就是如果有很多相同的点，并且这张子图是完全图，那么这就是一个完全图生成树计数的问题，根据$prufer$可以得出点数为$n$的完全图生成树计数为$n^{n-2}$...证明请见：http://www.matrix67.com/blog/archives/682

代码：

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

//by NeighThorn

#define pa pair<int,int>

#define inf 0x3f3f3f3f

#define mp make_pair

using namespace std;

const int maxn=100000+5,mod=1e9+7;

int n,tot,anscnt,a[maxn],s[maxn],t[maxn],fac[maxn];

long long sum;

struct Trie{

	int cnt,nxt[2];

}tr[maxn*30];

inline int read(void){

	char ch=getchar();int x=0;

	while(!(ch>='0'&&ch<='9')) ch=getchar();

	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();

	return x;

}

inline void init(void){

	for(int i=0;i<=tot;i++)

		tr[i].nxt[0]=tr[i].nxt[1]=tr[i].cnt=0;

	tot=0;

}

inline void insert(int x){

	int p=0;

	for(int i=30,y;i>=0;i--){

		y=(x>>i)&1;

		if(!tr[p].nxt[y])

			tr[p].nxt[y]=++tot;

		p=tr[p].nxt[y];

	}

	tr[p].cnt++;

}

inline pa find(int x){

	int p=0,ans=0;

	for(int i=30,y;i>=0;i--){

		y=(x>>i)&1;

		if(tr[p].nxt[y]) p=tr[p].nxt[y],ans|=y<<i;

		else p=tr[p].nxt[y^1],ans|=(y^1)<<i;

	}

	return mp(ans^x,tr[p].cnt);

}

inline int power(int x,int y){

	int res=1;

	while(y){

		if(y&1) res=1LL*res*x%mod;

		x=1LL*x*x%mod,y>>=1;

	}

	return res;

}

inline void solve(int l,int r,int dep){

	if(l>=r) return;

	if(dep<0){

		if(r-l+1>=2)

			anscnt=1LL*anscnt*power(r-l+1,r-l-1)%mod;

		return;

	}

	int cnt1=0,cnt2=0;

	for(int i=l;i<=r;i++)

		if((a[i]>>dep)&1) s[cnt1++]=a[i];

		else t[cnt2++]=a[i];

	for(int i=0;i<cnt1;i++) a[l+i]=s[i];

	for(int i=0;i<cnt2;i++) a[l+cnt1+i]=t[i];

	init();pa tmp;int ans=inf,cnt=0;

	for(int i=0;i<cnt2;i++) insert(t[i]);

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

		tmp=find(s[i]);

		if(tmp.first<ans)

			ans=tmp.first,cnt=tmp.second;

		else if(tmp.first==ans)

			cnt+=tmp.second;

	}

	if(sum!=inf&&cnt) sum+=ans,anscnt=1LL*cnt*anscnt%mod;

	solve(l,l+cnt1-1,dep-1);solve(l+cnt1,r,dep-1);

}

signed main(void){

	n=read(),anscnt=1;fac[0]=1;

	for(int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod;

	for(int i=1;i<=n;i++) a[i]=read();

	solve(1,n,30);

	printf("%lld\n%d\n",sum,anscnt);

	return 0;

}

By NeighThorn

巴特西

51Nod 1601 完全图的最小生成树计数

分析：

代码：

最新文章

热门文章