意思是:求 a 所有子集(可以为空)的异或值从小到大排序后,k 在其中第一次出现的位置(题目:P4869 albus就是要第一个出场)。
如果不考虑重复,计算排名时,
如果 k 某一位为 1,那么线性基中控制这一位的元素一定被选择,这样可以求出 在去重后的 中第一次出现的下标是多少。
for(int i=0;i<N;i++)
if(a[i]) b[cnt++]=i;
for(int i=0;i<cnt;i++)
if((k>>b[i])&1) ans+=(1ll<<i),ans%=mod;
为什么不用把线性基消成每位独立的再这么做?也就是,为什么不用按本质不同异或第 k 小的做法,先:
for(int i=0;i<N;i++)
for(int j=i-1;j>=0;j--) if((a[i]>>j)&1) a[i]^=a[j];
使得每个 ai=0,其第 i 位的 1 在线性基中只出现一次,避免当前位的选择都不会影响下一位?QAQ