首页 > 代码库 > hdu 4901

hdu 4901

一个简单的dp,比赛的时候太坚信自己的小聪明没用二维数组一直WA到死;

#include<cstdio>#include<cstring>#define maxn 1009#define mod 1000000007using namespace std;int num[maxn];long long ci[maxn][1026],andci[maxn][1026];bool vis[1026];int main(){    int t,n;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        for(int i=1; i<=n; i++)            scanf("%d",&num[i]);        memset(andci,0,sizeof andci);        memset(ci,0,sizeof ci);        long long ans=0;        for(int i=1; i<=n; i++)        {            ci[i][num[i]]++;            for(int j=0; j<1024; j++)            {                if(ci[i-1][j]>0)                {                    ci[i][j^num[i]]+=ci[i-1][j];                }                ci[i][j]+=ci[i-1][j];                ci[i][j]%=mod;            }        }        for(int i=n; i>0; i--)        {            andci[i][num[i]]=1;            vis[num[i]]=1;            for(int j=0; j<1024; j++)            {                if(andci[i+1][j]>0)                {                    andci[i][j&num[i]]+=andci[i+1][j];                    if(andci[i][j&num[i]]>mod)andci[i][j&num[i]]%=mod;                    vis[j&num[i]]=1;                }            }            for(int j=0; j<1024; j++)            {                ans+=(andci[i][j]*ci[i-1][j])%mod;                ans%=mod;            }            for(int j=0; j<1024; j++)            {                andci[i][j]+=andci[i+1][j];                if(andci[i][j]>mod)andci[i][j]%=mod;            }        }        printf("%I64d\n",ans);    }    return 0;}
View Code