分析
考虑建出一棵Trie,然后最小生成树就是0的部分到1的部分连一条边,
这个可以用区间短的一方查询另一棵trie,这样时间复杂度为 \(O(n\log^2{mx})\)
方案数注意相同的 \(n\) 个点的无根树为 \(n^{n-2}\)
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int N=3000011,mod=1000000007; long long ans;
int trie[N][2],L[N],R[N],tot=1,Ans=1,n,a[N];
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
int ksm(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;
}
void Insert(int x,int rk){
int p=1;
for (int i=29;~i;--i){
int z=(x>>i)&1;
if (!trie[p][z]) trie[p][z]=++tot;
p=trie[p][z],R[p]=rk;
if (!L[p]) L[p]=rk;
}
}
int query(int p,int dep,int x,int &C){
if (dep<0){
C=R[p]-L[p]+1;
return 0;
}
int z=(x>>dep)&1;
if (trie[p][z]) return query(trie[p][z],dep-1,x,C);
else return query(trie[p][z^1],dep-1,x,C)|(1<<dep);
}
long long dfs(int p,int dep){
if (dep<0){
int len=R[p]-L[p]+1;
if (len>2) Ans=1ll*Ans*ksm(len,len-2)%mod;
return 0;
}
int ls=trie[p][0],rs=trie[p][1],ans0=1<<30,ans1=0;
if (!ls) return dfs(rs,dep-1);
if (!rs) return dfs(ls,dep-1);
if (R[ls]-L[ls]>R[rs]-L[rs]) ls^=rs,rs^=ls,ls^=rs;
for (int i=L[ls],C;i<=R[ls];++i){
int now=query(rs,dep-1,a[i],C);
if (ans0>now) ans0=now,ans1=C;
else if (ans0==now) ans1=(ans1+C)%mod;
}
Ans=1ll*Ans*ans1%mod;
return dfs(ls,dep-1)+dfs(rs,dep-1)+ans0+(1<<dep);
}
int main(){
n=iut(),L[1]=1,R[1]=n;
for (int i=1;i<=n;++i) a[i]=iut();
sort(a+1,a+1+n);
for (int i=1;i<=n;++i) Insert(a[i],i);
ans=dfs(1,29);
return !printf("%lld\n%d",ans,Ans);
}