国外公司网站设计,教师专用ppt模板免费下载,良匠网站建设,徐州住房与城乡建设部网站正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId1601 题目大意 nnn个点的完全图#xff0c;边(i,j)(i,j)(i,j)的权值为aixoraja_i\ xor\ a_jai xor aj。求最小生成树和方案数。 解题思路
对于一个高位数#xff0c;将这一位为000和这一位为111分…正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId1601 题目大意
nnn个点的完全图边(i,j)(i,j)(i,j)的权值为aixoraja_i\ xor\ a_jai xor aj。求最小生成树和方案数。 解题思路
对于一个高位数将这一位为000和这一位为111分成两个点集那么显然是这些点集各构成一个最小生成树然后再这两个之间的连一条边。我们可以用TrieTrieTrie树找出这两个点集之间权值最小的一条边。
因最多分到logloglog层剩下的点集之间边权都为000所以我们只需要考虑如何求方案数。因为purferpurferpurfer序列所以nnn个点的完全图中的生成树数量为nn−2n^{n-2}nn−2
时间复杂度O(nloga)O(n\log a)O(nloga) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510,XJQ1e97;
ll n,a[N],S,ans,maxs,sol;
struct Trie{ll t[N*30][2],siz[N*30],cnt;void Clear(){cntt[1][0]t[1][1]0;return;}void Insert(ll x,ll val,ll dep){if(!x)xcnt,siz[x]t[x][0]t[x][1]0;siz[x];if(dep0)return;if((valdep)1)Insert(t[x][1],val,dep-1);else Insert(t[x][0],val,dep-1);}void Ask(ll x,ll val,ll dep,ll ans){if(!x)return;if(dep0){if(ansmaxs)maxsans,solsiz[x];else if(ansmaxs)solsiz[x];return;}ll w(valdep)1; if(t[x][w])Ask(t[x][w],val,dep-1,ans);else Ask(t[x][w^1],val,dep-1,ans|(1dep));return;}
}T;
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
void solve(ll dep,ll l,ll r){if(dep0){if(r-l0)S*power(r-l1,r-l-1);return;}ll cutr1;for(ll il;ir;i)if((a[i]dep)1){cuti;break;}if(cutl||cutr)solve(dep-1,l,r);else{T.Clear();ll rt0;for(ll il;icut;i)T.Insert(rt,a[i],30);maxs2147483647;sol1;for(ll icut;ir;i)T.Ask(rt,a[i],30,0);SS*sol%XJQ;ansmaxs;solve(dep-1,l,cut-1);solve(dep-1,cut,r);}return;
}
int main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%lld,a[i]);sort(a1,a1n);S1;solve(30,1,n);printf(%lld\n%lld,ans,S);
}
