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