求问线性基求子集异或值排名 qwq
  • 板块学术版
  • 楼主lkytxdy
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/2/14 15:10
  • 上次更新2023/10/28 08:33:28
查看原帖
求问线性基求子集异或值排名 qwq
381985
lkytxdy楼主2022/2/14 15:10

意思是:求 aa 所有子集(可以为空)的异或值从小到大排序后,kk 在其中第一次出现的位置(题目:P4869 albus就是要第一个出场)。

如果不考虑重复,计算排名时,

如果 kk 某一位为 11,那么线性基中控制这一位的元素一定被选择,这样可以求出 在去重后的 中第一次出现的下标是多少。

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;

为什么不用把线性基消成每位独立的再这么做?也就是,为什么不用按本质不同异或第 kk 小的做法,先:

for(int i=0;i<N;i++)
	for(int j=i-1;j>=0;j--) if((a[i]>>j)&1) a[i]^=a[j];

使得每个 ai0a_i\neq 0,其第 ii 位的 11 在线性基中只出现一次,避免当前位的选择都不会影响下一位?QAQ

2022/2/14 15:10
加载中...