题目

分析

考虑 \(kruskal\) 的过程

我们选边从高位开始

当前位为 \(0\) 的放一边，为 \(1\) 的放另一边

将 \(0\) 的建一棵字典树， \(1\) 的匹配

因为是异或，那就走相同值的位，算能匹配到的最小值的个数

和与方案数都可以在这里计算

\(Code\)

#include<cstdio>

using namespace std;

typedef long long LL;

const LL P = 1e9 + 7;

const int N = 100005;

int n , cnt , su , a[N] , c[N] , d[N] , ts[N * 30] , t[N * 30][2];

LL ans = 1;

LL fpow(LL x , LL y)

{

	LL res = 1;

	while (y)

	{

		if (y & 1) res = res * x % P;

		y >>= 1 , x = x * x % P;

	}

	return res;

}

void insert(int x)

{

	int u = 0 , ch;

	for(register int i = 30; i >= 0; i--)

	{

		ch = (x >> i) & 1;

		if (!t[u][ch]) t[u][ch] = ++cnt;

		u = t[u][ch] , ts[u]++;

	}

}

int find(int x)

{

	int u = 0 , ch , res = 0;

	for(register int i = 30; i >= 0; i--)

	{

		ch = (x >> i) & 1;

		if (t[u][ch]) u = t[u][ch];

		else u = t[u][ch ^ 1] , res = res + (1 << i);

	}

	su = ts[u];

	return res;

}

LL solve(int l , int r , int w)

{

	if (l >= r) return 0;

	if (w == -1)

	{

		if (r - l - 1 > 0) ans = ans * fpow(r - l + 1 , r - l - 1) % P;

		return 0;

	}

	int tl = 0 , tr = 0;

	for(register int i = l; i <= r; i++)

	if (a[i] & (1 << w)) d[++tr] = a[i];

	else c[++tl] = a[i];

	for(register int i = 1; i <= tl; i++) a[l + i - 1] = c[i];

	for(register int i = 1; i <= tr; i++) a[l + tl - 1 + i] = d[i];

	int tmp;

	if (!tl || !tr) tmp = 0;

	else

	{

		int num = 0 , f; tmp = 2147483647 , cnt = 0;

		for(register int i = 1; i <= tl; i++) insert(c[i]);

		for(register int i = 1; i <= tr; i++)

		{

			su = 0 , f = find(d[i]);

			if (f < tmp) tmp = f , num = su;

			else if (tmp == f) num += su;

		}

		ans = ans * num % P;

		for(register int i = 0; i <= cnt; i++) ts[i] = t[i][0] = t[i][1] = 0;

	}

	return 1LL * tmp + solve(l , l + tl - 1 , w - 1) + solve(l + tl , r , w - 1);

} 

int main()

{

	freopen("jst.in" , "r" , stdin);

	freopen("jst.out" , "w" , stdout);

	scanf("%d" , &n);

	for(register int i = 1; i <= n; i++) scanf("%d" , &a[i]);

	printf("%lld\n" , solve(1 , n , 30));

	printf("%lld" , ans);

}

巴特西

JZOJ 5352. 【NOIP2017提高A组模拟9.7】计数题

题目

分析

\(Code\)

最新文章

热门文章