首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。