51Nod 1601 完全图的最小生成树计数 kruskal + trie异或运算贪心

## 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PI;
const int maxn = 1e5+5;
const int INF = 2e9;
const ll MOD = 1e9+7;
int n, sz, fac[35], rt;
ll ans,sum;
struct tree{
int l, r, cnt;
} tr[maxn*30];
ll quick_pow(ll x, ll y){
ll ans = 1;
while (y){
if (y & 1)
ans = ans * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return ans;
}
void insert(int &d, int dep, int v){
if (!d)
d = ++sz;
tr[d].cnt++;
if (dep < 0)
return;
if (v & fac[dep])
insert(tr[d].l, dep - 1, v);
else
insert(tr[d].r, dep - 1, v);
}
PI get(int x, int y, int dep){
if (dep < 0)
return make_pair(0, (ll)tr[x].cnt * tr[y].cnt % MOD);
PI ans = make_pair(INF, 0);
if (tr[x].l && tr[y].l || tr[x].r && tr[y].r){
if (tr[x].l && tr[y].l){
PI now = get(tr[x].l, tr[y].l, dep - 1);
if (now.first < ans.first)
ans = now;
else if (now.first == ans.first)
ans.second += now.second,ans.second %= MOD;
}
if (tr[x].r && tr[y].r){
PI now = get(tr[x].r, tr[y].r, dep - 1);
if (now.first < ans.first)
ans = now;
else if (now.first == ans.first)
ans.second += now.second,ans.second %= MOD;
}
}
else{
if (tr[x].l && tr[y].r){
PI now = get(tr[x].l, tr[y].r, dep - 1);
now.first += fac[dep];
if (now.first < ans.first)
ans = now;
else if (now.first == ans.first)
ans.second += now.second,ans.second %= MOD;
}
if (tr[x].r && tr[y].l){
PI now = get(tr[x].r, tr[y].l, dep - 1);
now.first += fac[dep];
if (now.first < ans.first)
ans = now;
else if (now.first == ans.first)
ans.second += now.second,ans.second %= MOD;
}
}
return ans;
}
void solve(int d, int dep){
if (dep < 0){
if (tr[d].cnt > 2)
sum = (ll)sum * quick_pow(tr[d].cnt, tr[d].cnt - 2) % MOD;
return;
}
if (tr[d].l)
solve(tr[d].l, dep - 1);
if (tr[d].r)
solve(tr[d].r, dep - 1);
if (tr[d].l && tr[d].r){
PI now = get(tr[d].l, tr[d].r, dep - 1);
ans += now.first + fac[dep];
sum = (ll)sum * now.second % MOD;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
fac[0] = 1;
for (int i = 1; i <= 30; i++)
fac[i] = fac[i - 1] * 2;
for (int i = 1, x; i <= n; i++){
cin >> x;
insert(rt, 30, x);
}
sum = 1;
solve(rt, 30);
cout << ans << endl;
cout << sum << endl;
return 0;
}

0 条评论