[原创]51nod 算法马拉松22 完全图的最小生成树计数 【Trie树+图论】

2017-03-06 20:44:59 Tabris_ 阅读数:1084


博客爬取于2020-06-14 22:41:28
以下为正文

版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/60594774


题目连接:http://www.51nod.com/contest/problem.html#!problemId=1601

------------------------------------------------------------------------------.
完全图的最小生成树计数
SkyDec (命题人)
基准时间限制:1 秒 空间限制:131072 KB 分值: 160

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

Input
第一行一个正整数n
第二行n个整数表示a[1…n]
1<=n<=10^5
0<=a[i]<2^30

Output
第一行输出边权和
第二行输出方案数

Input示例
5
2 2 3 4 5

Output示例
8
6

--------------------------------------------------------------------------------.
解题思路:

首先对于最小生成树来说边一定是最小了,
那么 我们只要将 树分成两个,使得一颗子树的高位为11,另一颗为00,显然最好仅用一条边将这两颗子树连接起来能使得最后的权值和最小,那么对于这两颗子树分别递归的用这种方法求解得到就一定是最小生成树了。

那么对于xorxor很容易想到0101字典树,

然后我们发现0101字典树的左右儿子就是我们需要分开的两颗子树,

那么我们只要对字典树树进行dfs遍历,然后遇到同时存在左右儿子的就去计算一下选择哪条边且有多少种选法,我们就能知道结果了

计算选择哪条边的时候,我们可以枚举一棵子树的每个叶子节点,然后通过字典树在另一颗子树中查找与其异或值最小的,然后记录就行了.

然后注意的是:
1. 本题需要读入优化
2. 位运算括起来,因为优先级地
3. 枚举节点的时候最好用启发式选择,选择叶子节点少的枚举.
4. 然后注意的是 点值相同的完全图共有nn2n^{n-2}颗生成树

附本题代码
——————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
# include <bits/stdc++.h>

using namespace std;

# define INF (~(1<<31))
# define INFLL (~(1ll<<63))
# define pb push_back
# define mp make_pair
# define abs(a) ((a)>0?(a):-(a))
# define min(a,b) ((a)<(b)?(a):(b))
# define lalal puts("*******");
# define s1(x) scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int N = 1e5+7;
const int MOD = 1e9+7;
const double eps = 1e-8;
const double Pi = acos(-1.0);
const double E = exp(1.0);

inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
void fre(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
template<typename T>inline T _gcd(T a,T b){return (b==0)?a:_gcd(b,a%b);}
template<typename T>inline T _lcm(T a,T b){return a/_gcd(a,b)*b;}
LL qmod(LL a,LL b,LL c){LL ret=1ll;while(b){if(b&1)ret=ret*a%c;b>>=1,a=a*a%c;}return ret;}
/***********************************************************************/
int trie[N*40][3],sum[N*40],val[N*40],to[N*40],cnt,weishu = 30-1;
LL ans,tot,ta,tt;

inline void insert(int x){
int now = 0;
for(int i=weishu,bt;i>=0;i--){
bt = 1-(0==(x&(1<<i)));
if(!trie[now][bt]) trie[now][bt]=++cnt;
now = trie[now][bt];
sum[now]++;
}
val[now]=x;
}

inline int query(int x,int pre){
int now = 0;
for(int i=weishu,bt;i>=0;i--){
bt = 1-(0==(x&(1<<i)));
if(!trie[now][bt]) bt = 1-bt;
if(now == pre) bt = 1-bt;
now = trie[now][bt];
}
return now;
}

void dfs2(int x,int &pre){
if(trie[x][0]) dfs2(trie[x][0],pre);
if(trie[x][1]) dfs2(trie[x][1],pre);

if(!trie[x][0]&&!trie[x][1]){
int now = query(val[x],pre);
if( ta==(val[now]^val[x])){
tt =(tt+1ll*sum[now]*sum[x]%MOD)%MOD;
// printf("%d %d ",sum[now],val[now]^val[x]);
// printf("%lld %lld<--\n",ta,tt);
}
if( ta>(val[now]^val[x])){
ta=(val[now]^val[x]);
tt=(1ll*sum[now]*sum[x])%MOD;
// printf("%d %d ",sum[now],val[now]^val[x]);
// printf("%lld %lld<--\n",ta,tt);
}
// printf("%d %d\n",now,x);
}
}

void dfs(int x){
if(trie[x][0]) dfs(trie[x][0]);
if(trie[x][1]) dfs(trie[x][1]);

if(trie[x][0]&&trie[x][1]){
ta = INF,tt=0;

if(to[trie[x][1]]<to[trie[x][0]])
dfs2(trie[x][1],x);
else dfs2(trie[x][0],x);
// puts("--");
ans+=ta;
tot=tot*tt%MOD;

}
else if(!trie[x][0]&&!trie[x][1]&&sum[x]>1)
tot=tot*qmod(1ll*sum[x],1ll*sum[x]-2,1ll*MOD)%MOD;
}

int dfs1(int x){
if(!trie[x][0]&&!trie[x][1])
return to[x]=1;
if(trie[x][0]) to[x]+=dfs1(trie[x][0]);
if(trie[x][1]) to[x]+=dfs1(trie[x][1]);
return to[x];
}

int main(){

int n;
while(~scanf("%d",&n)){
// memset(trie,0,sizeof(trie));
// memset(sum,0,sizeof(sum));
cnt = 0;
ans = 0ll,tot=1ll;

for(int i=1,x;i<=n;i++){
x=read();
insert(x);
}

// puts("No.:");for(int i=0;i<=cnt;i++) printf("%2d ",i);puts("");
// puts("tot:");for(int i=0;i<=cnt;i++) printf("%2d ",sum[i]);puts("");
// puts("val:");for(int i=0;i<=cnt;i++) printf("%2d ",val[i]);puts("");
// puts("lson");for(int i=0;i<=cnt;i++) printf("%2d ",trie[i][0]);puts("");
// puts("rson");for(int i=0;i<=cnt;i++) printf("%2d ",trie[i][1]);puts("");
//
// printf("%lld\n",qmod(sum[30],sum[30]-2,MOD));

dfs1(0);
dfs(0);
printf("%lld\n%lld\n",ans,tot);
}
return 0;
}