首页 > 代码库 > 【bzoj2844】 albus就是要第一个出场

【bzoj2844】 albus就是要第一个出场

2024-09-02 03:04:46   220人阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=2844 (题目链接)

题意

　　给出${n}$个数，它们可以异或出${n^2}$个数，将这些数从小到大排列起来，问${Q}$最早出现的位置。

Solution

　　原来线性基还有这种性质，我怎么不知道→_→

　　假设${n}$个数可以消出${k}$个线性基，那么显然会有${2^k}$个不同的亦或和，${n}$个数相互排列显然会有${2^n}$个。神奇的事情就在于每种亦或和居然是一样多的，也就是都是${2^{n - k}}$个。

　　所以这道题就这样做了，高斯消元消成对角矩阵，从高位往低位如果异或上这个数之后小于${Q}$，那就异或上它。于是我们可以得到一个二进制数，这个二进制数就是排在它前面的可以被异或出来的数的个数（注意这里并没有计算重复的），又因为每个异或和都出现了${2^{n-k}}$次，所以最后答案就是排在它前面的数的个数乘上${2^{n-k}}$再加上${1}$就是${Q}$最早出现的位置。

细节

　　注意${0}$是一种不同的异或和，也就是说${0}$这个异或和也出现了${2^{n-k}}$次。

代码

// bzoj2844#include<algorithm>#include<iostream>#include<cstdlib>#include<complex>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define MOD 10086#define inf 1ll<<60#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=100010;int a[maxn],bin[32],n,m,Q;void Gauss() {	m=0;	for (int i=bin[30];i;i>>=1) {		int j=m+1;		while (j<=n && !(a[j]&i)) j++;		if (j==n+1) continue;		swap(a[++m],a[j]);		for (j=1;j<=n;j++) if (j!=m && a[j]&i) a[j]^=a[m];	}}int power(int a,int b) {	int res=1;	while (b) {		if (b&1) res=res*a%MOD;		b>>=1;a=a*a%MOD;	}	return res;}int main() {	bin[0]=1;for (int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;	scanf("%d",&n);	for (int i=1;i<=n;i++) scanf("%d",&a[i]);	Gauss();	scanf("%d",&Q);	int now=0,ans=0;	for (int i=1;i<=m;i++) if ((now^a[i])<Q) ans=(ans+power(2,m-i))%MOD,now^=a[i];	if (Q!=0) ans=(ans+1)%MOD;	ans=(ans*power(2,n-m))%MOD;	printf("%d",(ans+1)%MOD);	return 0;}

 

【bzoj2844】 albus就是要第一个出场


联系
我们