首页 > 代码库 > hdu 4901

hdu 4901

思路:各种状态转移统计一下,然后乘啊乘。G++T了,C++过了。

这里解释下吧:

a[i][j]代表前i个中包含第i个且异或值为j的集合的个数

b[i][j]代表前i个全部的异或值为j的集合的个数(与a不同,这里包含了包含第i个和不包含第i的情况)

c[i][j]代表第i个到最后一个中,包含第i个且 与运算的值为j的集合个数(这里的确用不着)

d[i][j]代表第i个到最后一个中,全部与运算为j的集合个数(可包含i,也可不包含i)

我这里用的是a与d运算求结果,事实上也可用b与c来算。至于为什么乘啊乘应该不难理解吧,不理解自己想吧。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const long long M=1e9+7;
long long a[1111][1111],b[1111][1111],c[1111][1111],d[1111][1111];
int n,aa[1111];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&aa[i]);
        if(n==1||n==0)
        {
            printf("0\n");
            continue;
        }
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        memset(d,0,sizeof(d));
        a[1][aa[1]]=1;
        b[1][aa[1]]=1;
        for(int i=2;i<=n;i++)
        {
            a[i][aa[i]]+=1;
            b[i][aa[i]]+=1;
            for(int j=0;j<1024;j++)
            {
                if(b[i-1][j])
                {
                    a[i][j^aa[i]]+=b[i-1][j];
                    b[i][j^aa[i]]+=b[i-1][j];
                    b[i][j]+=b[i-1][j];
                    a[i][j^aa[i]]%=M;
                    b[i][j^aa[i]]%=M;
                    b[i][j]%=M;
                }
            }
        }
        c[n][aa[n]]=1;
        d[n][aa[n]]=1;
        for(int i=n-1;i>=1;i--)
        {
            c[i][aa[i]]+=1;
            d[i][aa[i]]+=1;
            for(int j=0;j<1024;j++)
            {
                if(d[i+1][j])
                {
                    c[i][j&aa[i]]+=d[i+1][j];
                    d[i][j&aa[i]]+=d[i+1][j];
                    d[i][j]+=d[i+1][j];
                    c[i][j&aa[i]]%=M;
                    d[i][j&aa[i]]%=M;
                    d[i][j]%=M;
                }
            }
        }
        long long ans=0;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<1024;j++)
            {
                if(a[i][j]&&d[i+1][j])
                {
                    ans+=a[i][j]*d[i+1][j];
                    ans%=M;
                }
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}