原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1601.html

题意

题解

　　首先我们考虑如何求答案。

　　我们将所有数字按照二进制位从高到低建到 Trie 上，按照 kruscal 思想，我们要保证先选较小的边。

　　于是我们很容易得出结论：在 Trie 上，设 $f(x) =$ 合并子树 $x$ 的所有叶子节点的代价，设 $L(x),R(x)$ 分别为 $x$ 的左右子树编号，则 $f(x)=f(L(x))+f(R(x))+Connect(L(x),R(x))$ 。其中 $Connect(a,b)$ 表示在 $a$ 的叶子节点中 和 $b$ 的叶子节点中各选择一个节点，并将他们相连，需要的最小代价。

　　这个显然非常容易求。

　　最后我们还有一个问题，就是当递归到 Trie 的叶子节点之后，我们发现它们代表的数字全部相同，连任意一条边的代价为 $0$ ，求把它们连成一棵树的方案，就相当于有 $k$ 个点的无根树计数。有一个东西叫做 pruffer 编码，通过这个东西可以得到 $k$ 个点的互不相同的带标号无根树个数为 $k^{k-2}$ 。

　　于是问题就解决了。

代码

#include 
     
      using namespace std;typedef long long LL;const int N=100005,S=N*30,mod=1e9+7;LL read(){	LL x=0,f=1;	char ch=getchar();	while (!isdigit(ch)&&ch!='-')		ch=getchar();	if (ch=='-')		f=-1,ch=getchar();	while (isdigit(ch))		x=(x<<1)+(x<<3)+ch-48,ch=getchar();	return x*f;}int Next[S][2],tot[S],depth[S],flag[S],cnt=1;int Pow(int x,int y){	int ans=1;	for (;y;y>>=1,x=1LL*x*x%mod)		if (y&1)			ans=1LL*ans*x%mod;	return ans;}LL ans1=0,ans2=1;void build(int v){	int x=1,t;	for (int i=29;i>=0;i--){		t=(v>>i)&1;		if (!Next[x][t])			Next[x][t]=++cnt;		x=Next[x][t];		depth[x]=i,flag[x]=t;	}	tot[x]++;}int mindif,situ;void Min_Cost_Merge(int x,int y,int dif){	dif|=(flag[x]^flag[y])<
      
       0&&Next[y][t^k]>0)				Min_Cost_Merge(Next[x][t],Next[y][t^k],dif),f=1;		if (f)			return;	}	if (dif
       
        1)		ans2=1LL*ans2*Pow(tot[x],tot[x]-2)%mod;	if (s==2){		mindif=1<<30,situ=1;		Min_Cost_Merge(Next[x][0],Next[x][1],0);		ans1+=mindif,ans2=1LL*ans2*situ%mod;	}	return 1;}int main(){	memset(tot,0,sizeof tot);	memset(Next,0,sizeof Next);	for (int i=1,n=read();i<=n;i++)		build(read());	solve(1);	printf("%lld\n%lld",ans1,ans2);	return 0;}