BZOJ2844: albus就是要第一个出场(线性基)
2018-06-17 20:25:56来源:未知 阅读 ()
Submit: 2054 Solved: 850
[Submit][Status][Discuss]
Description
Input
第一行一个数n, 为序列A的长度。接下来一行n个数, 为序列A, 用空格隔开。最后一个数Q, 为给定的数.
Output
Sample Input
1 2 3
1
Sample Output
样例解释:
N = 3, A = [1 2 3]
S = {1, 2, 3}
2^S = {空, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
f(空) = 0
f({1}) = 1
f({2}) = 2
f({3}) = 3
f({1, 2}) = 1 xor 2 = 3
f({1, 3}) = 1 xor 3 = 2
f({2, 3}) = 2 xor 3 = 1
f({1, 2, 3}) = 0
所以
B = [0, 0, 1, 1, 2, 2, 3, 3]
HINT
数据范围:
1 <= N <= 10,0000
其他所有输入均不超过10^9
Source
湖北省队互测
// luogu-judger-enable-o2 #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define int long long using namespace std; const int MAXN = 1e5 + 10, B = 61, mod = 10086; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, a[MAXN], P[MAXN]; void Insert(int x) { for(int i = B; i >= 0; i--) { if((x >> i) & 1) { if(!P[i]) {P[i] = x; return ;} x = x ^ P[i]; } } } void Gauss() { for(int i = B; i >= 0; i--) if(P[i]) for(int j = i + 1; j <= B; j++) if((P[j] >> i) & 1) P[j] ^= P[i]; } int num = 0, pos[MAXN]; void ReMove() { for(int i = 0; i <= B; i++) if(P[i]) pos[++num] = i; } int fastpow(int a, int p) { int base = 1; while(p) { if(p & 1) base = (base * a) % mod; a = (a * a) % mod; p >>= 1; } return base; } main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif N = read(); for(int i = 1; i <= N; i++) a[i] = read(), Insert(a[i]); Gauss(); ReMove(); int Q = read(), ans = 0; for(int i = 1; i <= num; i++) if((Q & (1ll << pos[i]))) ans = ans ^ (1 << i - 1); printf("%lld\n", (ans * fastpow(2, N - num) + 1) % mod); }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 全排列问题 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash