博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces957 Mahmoud and Ehab and yet another xor task
阅读量:5008 次
发布时间:2019-06-12

本文共 1847 字,大约阅读时间需要 6 分钟。

题意:长度为n的序列,q个查询,每次查询一个l,x问[1, l]中子序列异或出来等于x的个数

题解:这道题可以用线性基来处理

线性基是一个集合,它异或出来的集合与原集合异或相同

原集合异或出来的数可以由线性基唯一表示

一个数能遍历线性基得到0,这个数就可以被异或出来

那么这道题可以离线处理,对于每一个查询[l ,x],已经处理出来[1, l]的线性基,那么遍历一遍后可以知道x能否表示

计算个数的时候,因为一个线性基代表一个数,所以遍历后的num就是表示x所需要的数,而剩下的l-num个数,如果可以表示为y,那么这l个数就一定可以表示出y^x(因为前面是已经判断过x一定给可以表示)

所以答案就是2^(l-num)

#include 
#define maxn 100010#define INF 0x3f3f3f3ftypedef long long ll;using namespace std;int num;struct L_B{ ll d[61],p[61]; int cnt; L_B() { memset(d,0,sizeof(d)); memset(p,0,sizeof(p)); cnt=0; } bool insert(ll val) { for (int i=60;i>=0;i--) if (val&(1LL<
0; } ll query_max() { ll ret=0; for (int i=60;i>=0;i--) if ((ret^d[i])>ret) ret^=d[i]; return ret; } ll query_min() { for (int i=0;i<=60;i++) if (d[i]) return d[i]; return 0; } void rebuild() { for (int i=60;i>=0;i--) for (int j=i-1;j>=0;j--) if (d[i]&(1LL<
=(1LL<
=0;i--) if (k&(1LL<
=0;i--){ if(d[i]){ num++; if(x&(1LL<
=0;i--) if (n2.d[i]) ret.insert(n1.d[i]); return ret;}ll f(ll a,ll b){ ll mod = 1e9+7; a %= mod; ll ans = 1; while(b){ if(b&1) ans = ans*a%mod; a = a*a%mod; b >>= 1; } return ans;}ll a[maxn], ans[maxn], l, x;vector
>G[maxn];int main(){ ll n, q; cin>>n>>q; for(int i=1;i<=n;i++) scanf("%lld", &a[i]); for(int i=1;i<=q;i++){ scanf("%lld%lld", &l, &x); G[l].push_back(make_pair(i, x)); } for(int i=1;i<=n;i++){ b.insert(a[i]); for(auto j:G[i]){ if(b.query(j.second)) ans[j.first] = f(2, (i-num)); } } for(int i=1;i<=q;i++) cout<
<

 

转载于:https://www.cnblogs.com/Noevon/p/8733910.html

你可能感兴趣的文章
一套超棒的免费迷你OS图标
查看>>
windows mysql服务器
查看>>
暑假第七周总结
查看>>
使用Django实现分页器功能
查看>>
scss常规用法
查看>>
css定位position属性深究
查看>>
android中不同版本兼容包的区别
查看>>
阿里云配置HTTPS
查看>>
web总结
查看>>
ZeroMQ接口函数之 :zmq_plain - 明文认证
查看>>
jQuery和js之Cookie实现
查看>>
接口相关测试点
查看>>
初始化日期为yyyy-MM-dd HH:mm:ss格式
查看>>
Codeforces Round #316 (Div. 2) C. Replacement(线段树)
查看>>
UI 中的 结构体 字符串的 初始化
查看>>
android之PackageManager简介
查看>>
sql查询删除重复数据
查看>>
checkstyle配置文件说明
查看>>
cmake编译opencv时指定cuda版本
查看>>
固态硬盘装系统/双系统
查看>>