ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[牛客竞赛]Xor序列(线性基 + 数学)

2022年8月3日 124点热度 0人点赞 0条评论

题目传送门:H-xor序列

思路 / Thought

求线性基然后判断x ^ y能否被线性表示即可,因为若x ^ z = y则有z = x ^ y也就是说线性基能够表示x ^ y。

关于线性基参考这篇文章《[数学基础 & 模板]Xor Linear Basis异或线性基学习笔记》

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 70, MAXL = 63;
int p[maxn], d[maxn], tot, N;

void ins(int x)
{
	for(int i = MAXL;i >= 0; -- i)//Traverse from back to front
	{
		if(!x)return;
		if(!(x >> i & 1))continue;
		
		if(p[i])x ^= p[i];
		else return p[i] = x, void();
	}
}

void rebuild()
{
	tot = 0;
	for(int i = 0;i <= MAXL; ++ i)
	{
		for(int j = 0;j < i; ++ j)if(p[i] >> j & 1)p[i] ^= p[j];
		if(p[i])d[tot ++] = p[i];//the idx of d is from 0 to (tot - 1)
	}
}

bool isok(int x)
{
	for(int i = MAXL;i >= 0; -- i)
	{
		if(!(x >> i & 1))continue;
		
		if(p[i])x ^= p[i];
		else return false;//the x could not be represented by Linear Basis
	}
	return true;//could
}

signed main()
{
	ios::sync_with_stdio(0);
	cin >> N;//the count of elements
	for(int i = 1;i <= N; ++ i)
	{
		int x;cin >> x;
		ins(x);//insert x into the Linear Basis
	}
	rebuild();//do not forget to rebuild
	int M;cin >> M;//M is the count of query
	while(M --)
	{
		int x, y;cin >> x >> y;
		cout << (isok(x ^ y) ? "YES" : "NO") << '\n';
	}
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 数学 牛客网 算法竞赛 线性基
最后更新:2022年8月3日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号