2019 Nowcoder Multi-University Training Contest 1 H-XOR
由于每个元素贡献是线性的,那么等价于求每个元素出现在多少个异或和为$0$的子集内。因为是任意元素可以去异或,那么自然想到线性基。
先对整个集合A求一遍线性基,设为$R$,假设$R$中元素个数为$r$,那么任取一个不在$R$内的元素,$R$中肯定存在一种取法能和这个元素异或和为$0$。
同理,取定一个不在$R$内的元素,再随便取另外任意个不在$R$内的元素,$R$内仍然存在一种取法使得这个异或和为$0$。那么每个不在$R$内的元素包含在$2^{n - r - 1}$个集合内(其他不在$R$内的元素可以任取)。所以所有不在$R$内的元素对答案的贡献就是$\left(n - r + 1\right) \times 2^{n - r + 1}$。
考虑在$R$内的元素,最多只有$62$个元素。它们对答案的贡献其实就跟上面的一样。
对不在线性基内的元素求一遍线性基,设为$other$,这样其实就缩成了$2$个包含$62$个元素的集合。枚举$R$的每个元素$a_i$,把其他$123$个元素加入一个线性基中,设这个线性基为$temp$,元素个数为$r'$,最后看$a_i$能否加入线性基中,如果不行就说明$temp$能让它异或和为$0$。同理可得对答案的贡献为$2^{n - r' - 1}$。
其实到这我只check了$a_i$能否加入$temp$,并没有check另外$n - r' - 1$个元素能否加入$temp$,但是其实在之前已经check过了,对于在$R$内和$other$的其他元素显然,因为我暴力枚举了它们去加入$temp$。对于其他元素其实都已经在得到$R$和$other$的时候尝试着让它们加入$R$和$other$,那么它们其实也是不能加入$temp$的。
#include <bits/stdc++.h>
#define ll long long
using namespace std; const int sz = ;
const int N = 1e5 + ;
const ll MOD = 1e9 + ;
bool vis[N];
vector<ll> G;
ll a[N], bin[N]; struct XO {
ll p[sz];
void init() {
memset(p, , sizeof(p));
}
bool ins(ll x) {
for (int i = ; ~i; i--)
if (x >> i & ) {
if (!p[i]) { p[i] = x; return true; }
x ^= p[i];
}
return false;
}
} R, other, temp; int main() {
int n;
bin[] = ;
for (int i = ; i < N; i++) bin[i] = bin[i - ] * % MOD;
while (~scanf("%d", &n)) {
R.init(); other.init();
G.clear();
int r = ;
for (int i = ; i <= n; i++) {
scanf("%lld", &a[i]);
vis[i] = ;
if (R.ins(a[i])) {
r++;
vis[i] = ;
G.push_back(a[i]);
}
}
if (r == n) {
puts("");
continue;
}
ll ans = (n - r) * bin[n - r - ] % MOD;
for (int i = ; i <= n; i++) {
if (!vis[i]) other.ins(a[i]);
}
for (auto x: G) {
int tol = ;
temp.init();
for (auto y: G) {
if (x == y) continue;
if (temp.ins(y)) tol++;
}
for (int i = ; i <= ; i++) {
if (temp.ins(other.p[i])) tol++;
}
if (!temp.ins(x)) ans = (ans + bin[n - tol - ]) % MOD;
}
printf("%lld\n", ans);
}
return ;
}
最新文章
- Android下/data/data/<;package_name>;/files读写权限
- 【BZOJ4008】[HNOI2015]亚瑟王 期望
- console中一些不常用的实用方法
- ASP.NET MVC的处理管线
- 12.allegro环境设置[原创]
- Java was started but returned exit code=13 C:\ProgramData\Oracle\Java\javapath\javaw.exe
- Objective-C 内存管理之 _ARC
- Android开发之自己主动登录功能的实现
- ADO.NET中的DataSet和DataReader
- arm-none-eabi-g++ -Xlinker -T ";../LF3Kmonitor.ld"; -Xlinker -Map=";Bogota_ICT_V.map";-ram-hosted.ld -mc
- deque源码4(deque元素操作:pop_back、pop_front、clear、erase、insert)
- JS典记
- websocket是什么
- ABP框架系列之二十六:(EventBus-Domain-Events-领域事件)
- 胜利大逃亡 HDU1429 (bfs)
- pycharm的安装(图文)
- 【linux基础】生成目录下所有图片的路径
- dubbo学习思路梳理
- python学习(21) smtp发送邮件
- Java 对象初始化生命周期