【NOIP模拟赛】序列问题

2014年11月4日2,0530

【题目描述】

小H是个善于思考的学生,她正在思考一个有关序列的问题。

她的面前浮现出了一个长度为n的序列{ai},她想找出两个非空的集合S、T。

这两个集合要满足以下的条件:

  1. 1. 两个集合中的元素都为整数,且都在 [1, n] 里,即Si,Ti ∈ [1, n]。
  2. 2. 对于集合S中任意一个元素x,集合T中任意一个元素y,满足x < y。
  3. 3. 对于大小分别为p, q的集合S与T,满足

        a[s1] xor a[s2] xor a[s3] … xor a[sp] = a[t1] and a[t2] and a[t3] … and a[tq].

小H想知道一共有多少对这样的集合(S,T),你能帮助她吗?

【输入格式】

第一行,一个整数n

第二行,n个整数,代表ai。

【输出格式】

仅一行,表示最后的答案。

【样例输入】

4

1 2 3 3

【样例输出】

4

【样例解释】

S = {1,2}, T = {3}, 1 ^ 2 = 3 = 3 (^为异或)

S = {1,2}, T = {4},  1 ^ 2 = 3 = 3

S = {1,2}, T = {3,4}  1 ^ 2 = 3 & 3 = 3 (&为与运算)

S = {3}, T = {4}  3 = 3 = 3

【数据范围】

30%: 1 <= n <= 10

60%: 1 <= n <= 100

100%: 1 <= n <= 1000, 0 <= ai < 1024

题解

暴力30分把子序列搜索出来然后枚举断点。。。

然后异或以及和运算都可以dp出来

f[i][j]表示前i个数集合异或/和的值为j,且i在集合中的方案

但是答案很大,还要压位高精,数组还需要滚动

好麻烦。。

只写了50分