大意: 给定序列, 求所有异或和为$0$的子序列大小之和.

先求出线性基, 假设大小为$r$.

对于一个数$x$, 假设它不在线性基内, 那么贡献为$2^{n-r-1}$

因为它与其余不在线性基内数的任意组合后均可以与线性基异或后变为$0$, 产生$1$的贡献.

所以问题就转化为求多少个数可以不在线性基内.

现任意求出一组线性基, 然后再暴力验证该组线性基内的数即可.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <bitset>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head const int N = 1e5+10;
int n, vis[N];
ll a[N];
struct _ {
ll a[66];
_ () {memset(a,0,sizeof a);}
inline bool ins(ll x) {
REP(i,1,*a) x=min(x,a[i]^x);
return x?a[++*a]=x:0;
}
inline _ operator + (const _ &rhs) const {
_ r;
REP(i,0,*a) r.a[i]=a[i];
REP(i,1,rhs.a[0]) r.ins(rhs.a[i]);
return r;
}
inline int chk(ll x) {
REP(i,1,*a) x=min(x,a[i]^x);
return !x;
}
} pre[N], suf[N]; int main() {
while (~scanf("%d", &n)) {
REP(i,1,n) {
scanf("%lld", a+i);
if ((pre[i]=pre[i-1]).ins(a[i])) vis[i] = 1;
}
if (pre[n].a[0]==n) {
puts("0");
continue;
}
suf[n+1] = _();
PER(i,1,n) (suf[i]=suf[i+1]).ins(a[i]);
int sum = 0;
REP(i,1,n) {
if (!vis[i]) ++sum;
else {
vis[i] = 0;
if ((pre[i-1]+suf[i+1]).chk(a[i])) ++sum;
}
}
int ans = sum*qpow(2,n-pre[n].a[0]-1)%P;
printf("%d\n", ans);
}
}

最新文章

  1. PHP-Redis扩展使用手册(三)
  2. java 验证码
  3. NuGet学习笔记(1) 初识NuGet及快速安装使用
  4. C# 操作网页标签
  5. 总结 | 如何测试你自己的 RubyGem
  6. win32空项目创建窗体
  7. Markdown 使用说明
  8. 2、Spring的 IoC详解(第一个Spring程序)
  9. Matlab将三维变量分割为多个二维变量的方法
  10. C#图解教程
  11. Java作业-网络编程
  12. Java中堆(heap)和栈(stack)的区别
  13. JS中 confirm() 方法
  14. 使用antd-mobile的ImagePicker组件实现图片的上传
  15. Python学习笔记_week2_列表、元组、字典、字符串、文件、i编码
  16. lambda表达式(c++11)
  17. MQTT协议笔记之mqtt.io项目TCP协议支持
  18. MAC软件工具下载
  19. C#语言 ArrayList集合
  20. jvm 命令

热门文章

  1. 解决微信小程序要求TLS版本不低于1.2问题
  2. ngx.shared.DICT.set
  3. 解决用root用户及密码可以直接登陆某LINUX系统,但是用ssh登陆,系统却总是提示密码不对
  4. Git如何永久删除某个重要文件文件或文件夹 (包括历史记录) 强制
  5. es6对象复制合并 Object.assign
  6. Map接口和Collection接口的区别
  7. NPM 私服
  8. c# 结构体struct注意事项
  9. iOS从App跳转至系统设置菜单各功能项
  10. iOS-UINavigationController多控制器管理