题意

给定一个长度为n的数组a[1..n]，有一幅完全图，满足(u,v)的边权为a[u] xor a[v]
求边权和最小的生成树，你需要输出边权和还有方案数对1e9+7取模的值

题解

考虑贪心
先建立字典树
对于字典树上的每一个点，他子树的生成树肯定是
s1的生成树+s2的生成树+s1到s2的最小边
前两个都是子问题
s1到s2的最小边可以用启发式合并来解决

CODE:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL MOD=1e9+7;
const LL size=30;
const LL N=100005;
const LL MAX=(1LL<<35);
LL n;
struct qq {LL son[2];LL tot;///如果他是叶子，那他有多少个人 LL x;//这个点是第几位 }tr[N*32];LL num=0;
void Ins (LL x)
{LL now=0;for (LL u=size;u>=0;u--){LL t=(x&(1<<u));if (t!=0) t=1;if (tr[now].son[t]==0) {tr[now].son[t]=++num;tr[num].x=u;}now=tr[now].son[t];}tr[now].tot++;
}
LL tot[N*32];
LL ans=0;
LL ans1=1;
LL lalal=MAX,ooo=0;
void Dfs (LL x,LL y,LL now)
{
//  printf("%I64d %I64d\n",x,y);LL s1=tr[x].son[0],s2=tr[x].son[1];LL S1=tr[y].son[0],S2=tr[y].son[1];if (s1==0&&s2==0){if (now<lalal) lalal=now,ooo=0;if (now==lalal) {ooo=(ooo+tr[x].tot*tr[y].tot%MOD)%MOD;}return ;}if (s1!=0){if (S1!=0) Dfs(s1,S1,now);else Dfs(s1,S2,now+(1<<tr[s1].x));}if (s2!=0){if (S2!=0) Dfs(s2,S2,now);else Dfs(s2,S1,now+(1<<tr[s2].x));}
}
LL pow(LL x,LL y)
{
//  printf("%I64d %I64d\n",x,y);if (y<=0) return 1;if (y==1) return x;LL lalal=pow(x,y>>1);lalal=lalal*lalal%MOD;if (y&1) lalal=lalal*x%MOD;return lalal;
}
void dfs1 (LL x)
{tot[x]=1;LL s1=tr[x].son[0],s2=tr[x].son[1]; if (s1==0&&s2==0) {ans1=ans1*pow(tr[x].tot,tr[x].tot-2)%MOD;return ;}else if (s1==0) {dfs1(s2);tot[x]+=tot[s2];}else if (s2==0) {dfs1(s1);tot[x]+=tot[s1];}else{dfs1(s1);dfs1(s2);tot[x]+=tot[s1];tot[x]+=tot[s2];lalal=MAX;ooo=0;if (tot[s1]<tot[s2]) Dfs(s1,s2,0);else Dfs(s2,s1,0);lalal+=(1<<tr[s1].x);ans=ans+lalal;ans1=ans1*ooo%MOD;}
}
int main()
{freopen("a.in","r",stdin);scanf("%I64d",&n);for (LL u=1;u<=n;u++){LL x;scanf("%I64d",&x);Ins(x); }dfs1(1);printf("%I64d\n%I64d\n",ans,ans1);return 0;
}