本文共 1023 字，大约阅读时间需要 3 分钟。

参考博客： orz

下面的题解来着该博客

给定 n(n≤100000) 个数 a1, a2, …, an，以及一个数 Q。将 a1, a2, …, an 的所有子集（可以为空）的异或值从小到大排序得到序列 B，请问 Q 在 B 中第一次出现的下标是多少？保证 Q 在 B 中出现。

分析

如果去除序列 B 中重复的数，使用线性基，根据 Q 的二进制位便可以确定 Q 的排名。可是如果不去重，怎么才能知道每个数出现多少次呢？

结论：每个数都出现一样的次数，且这个次数为 2^(​n−∣B∣)。

这样就只需要一个快速幂就能快速计算答案了。

我的代码：

#include
   
    #include
    
     using namespace std;const int maxn=100000+100;const int mod=10086;int ans[maxn],ind=1;bool vis[35];int tmp[35];int n,Q;void gauss(){		for(int i=30,j;i>=0;i--){				for(j=ind;j<=n;j++) if(ans[j]&(1<
     
      >=1;	}	return mul;}int main(){		scanf("%d",&n);	for(int i=1;i<=n;i++) scanf("%d",&ans[i]);	scanf("%d",&Q);	gauss();	int rank=0;	int tot=0;	for(int i=0;i<=30;i++) if(vis[i]) tmp[tot++]=i;	for(int i=0;i
      
       >tmp[i]&1) rank+=(1<
      
     
    
   

转载地址：https://kaven.blog.csdn.net/article/details/81220587 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！