BZOJ3866:The Romantic Hero dp

思路:

令\(f[i][j]\)表示最后一个数的位置\(\leq{i}\),异或起来等于\(j\)的序列数,\(g[i][j]\)表示第一个数的位置\(\geq{i}\),与起来等于\(j\)序列数.

我们差分之后就很容易得到结尾、开头位置确定的异或、与的序列个数了.

这两个东西知道之后,随便维护个前缀和什么的就行了.

(大常数\(O(n^2)\),目前倒数第一)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
  
#define N 1010
#define M 1024
int f[N][M],g[N][M],a[N],add[M][N];
  
static const int mod=(1e9)+7;
  
inline void inc(int&x,int y){if((x+=y)>=mod)x-=mod;}
inline int dec(int x,int y){return (x-y+mod)%mod;}
int main(){
    int T;scanf("%d",&T);
    register int i,j;int n;
    while(T--){
        scanf("%d",&n);for(i=1;i<=n;++i)scanf("%d",&a[i]);
        for(memset(f,0,sizeof f),i=1;i<=n;++i){
            inc(f[i][a[i]],1);
            for(j=0;j<M;++j)inc(f[i][a[i]^j],f[i-1][j]);
            for(j=0;j<M;++j)inc(f[i][j],f[i-1][j]);
        }
        for(memset(g,0,sizeof g),i=n;i>=1;--i){
            inc(g[i][a[i]],1);
            for(j=0;j<M;++j)inc(g[i][a[i]&j],g[i+1][j]);
            for(j=0;j<M;++j)inc(g[i][j],g[i+1][j]);
        }
          
        for(i=n;i>=1;--i)for(j=0;j<M;++j)f[i][j]=dec(f[i][j],f[i-1][j]);
        for(i=1;i<=n;++i)for(j=0;j<M;++j)g[i][j]=dec(g[i][j],g[i+1][j]);
          
        for(j=0;j<M;++j)for(i=n;i>=1;--i)add[j][i]=add[j][i+1],inc(add[j][i],g[i][j]);
          
        int ans=0;
        for(j=0;j<M;++j)for(i=1;i<=n;++i)inc(ans,(long long)f[i][j]*add[j][i+1]%mod);
          
        printf("%d\n",ans);
    }
      
    return 0;
}