序列问题

【题目描述】

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

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

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

1. 两个集合中的元素都为整数，且都在 [1, n] 里，即Si，Ti ∈ [1, n]。

2. 对于集合S中任意一个元素x，集合T中任意一个元素y，满足x < y。

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。

【输出格式】

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

【样例输入】

1 2 3 3

【样例输出】

【样例解释】

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，考试时也想到了，但是状态定义的不好没所以很慢，题解的状态很巧妙，异或和与的情况分别定义。
   两个数相等就相当于两个数的 xor 为 0。设 f[i][j][k=0..2]代表 处理到第i个数，如果 k=1 代表 and 值为 j,如果 k=2 代表 xor 值为 j,如果 k= 0 则代表一个元素都没取。所以很容易得到方程：
f[i][j][0] = f[i + 1][j][0]
f[i][j & ai][1] = f[i + 1][j][1] + f[i + 1][j][0] + f[i + 1][j & ai][1]
f[i][j ^ ai][2] = f[i + 1][j][1] + f[i + 1][j][2] + f[i + 1][j ^ ai][2];
最后 f[1][0][2]就是答案。
由于高精度要压位，所以没打。
*/
#include<cstdio>
#include<iostream>
#define N 1500
#define lon long long
using namespace std;
int a[N],n;
lon f[2][N][3];
int main(){
    //freopen("sequence.in","r",stdin);
    //freopen("sequence.out","w",stdout);
    freopen("jh.in","r",stdin);
    scanf("%d",&n);
    for(int i=n;i;--i) scanf("%d",&a[i]);
    f[0][1023][0]=1LL;
    int nxt=0,cur=0;
    for(int i=0;i<n;++i){
        nxt=cur^1;
        for(int j=0;j<=1023;++j)
            for (int k=0;k<=2;++k)
                f[nxt][j][k]=f[cur][j][k];
        for (int j=0;j<=1023;++j) {
            int va=a[i+1]&j,vx=a[i+1]^j;
            f[nxt][va][1]+=f[cur][j][0];f[nxt][va][1]+=f[cur][j][1];
            f[nxt][vx][2]+=f[cur][j][1];f[nxt][vx][2]+=f[cur][j][2];
        }
        cur^=1;
    }
    cout<<f[cur][0][2];
    return 0;
}