本文共 1425 字，大约阅读时间需要 4 分钟。
第一行一个数n, 为序列A的长度。接下来一行n个数， 为序列A， 用空格隔开。最后一个数Q， 为给定的数.
题意：
给定n个数以及一个数q，将这n个数的所有子集（可以为空）的异或值从小到大排序得到序列B（这样B内就有2^n 个 元素），求出q在序列B中第一次出现的下标，答案对10086取膜（默认q一定存在）
思路：
这题要解决两个问题：
①B序列去重之后，q在B中是第几个
②B序列中每个数字出现多少次
对于问题①，如何求出去重后B数组的第k小，而这题其实是反过来的给你一个数q，求出它是第几小
其实也很简单，把操作也反过来就行了，你甚至不用求出行最简式矩阵
步骤：1. 求出线性基后线性基内所有元素从小到大排序，并且只保留最高位
2. 之后将q二进制拆分，初始化rank=0，如果q的第i位为1，就看线性基中是否存在一个数x满足x = (1<<i)，如果存在，那么rank = rank^(x在线性基中排名)，最后的rank就是q的排名-1，为什么是排名-1呢因为还有个0没有算
对于问题②，定理：B数列中每个数字出现次数都是2^(n-cnt)！其中cnt是线性基的大小
有了这个定理问题②其实就解决了，这样原问题答案就是rank*2^(n-cnt)+1，一个快速幂就可以解决
证明如下：
还记得这道题么：
这道题是求n个数有多少个集合满足异或为0，如果包含空集答案就是2^(n-cnt)
而有个性质：线性基内任意集合异或结果唯一，而所有数异或0还是本身
所以每个数字出现的个数就等于(1*异或值为0的集合个数) = 2^(n-cnt)
证毕
#include#include using namespace std;#define mod 10086int a[100005], p[35], jz[35];int Pow(int x, int y){ int ans = 1; while(y) { if(y%2) ans = ans*x%mod; x = x*x%mod; y /= 2; } return ans;}int main(void){ int n, i, j, cnt, K, q; scanf("%d", &n); for(i=1;i<=n;i++) scanf("%d", &a[i]); for(i=1;i<=n;i++) { for(j=30;j>=0;j--) { if(a[i]&(1<
转载地址：http://nmmgf.baihongyu.com/