51nod 算法马拉松22 完全图的最小生成树计数 【Trie树+图论】
题目连接：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
——————————————————————————–. 解题思路：
首先对于最小生成树来说边一定是最小了,
那么 我们只要将 树分成两个,使得一颗子树的高位为
那么对于
然后我们发现
那么我们只要对字典树树进行dfs遍历,然后遇到同时存在左右儿子的就去计算一下选择哪条边且有多少种选法,我们就能知道结果了
计算选择哪条边的时候,我们可以枚举一棵子树的每个叶子节点,然后通过字典树在另一颗子树中查找与其异或值最小的,然后记录就行了.
然后注意的是:
1. 本题需要读入优化
2. 位运算括起来,因为优先级地
3. 枚举节点的时候最好用启发式选择,选择叶子节点少的枚举.
4. 然后注意的是 点值相同的完全图共有
附本题代码 ——————————————————————————————————
#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; }