注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4901 The Romantic Hero  

2014-08-01 09:24:44|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4901
多校合练第四场第5题。
题意:
有n个数,取数组成两个集合S和T,S集合里的元素位置上比T靠前,问有多少种取法使得S集合里所有元素异或值等于T集合里所有元素取与的值。
从前往后dp记录第第i个数与前i-1个数异或值为j的个数,前i个数异或值为j的个数;
从后往前dp记录i+1到n的与值为j的个数。

#define vN 1050
int n,base[vN];
LL Xor[vN][vN], And[vN][vN],XXor[vN][vN];

//Xor记录第i个数与前i-1个数异或值为j的个数

//XXor记录前i个数异或值为j的个数
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
memset(Xor, 0, sizeof(Xor));
memset(And, 0, sizeof(And));
memset(XXor,0,sizeof(XXor));
for (int i = 1; i <= n; i++)
scanf("%d", &base[i]);
for (int i = 1; i <= n; i++)
{
Xor[i][base[i]]++;
XXor[i][base[i]]++;
for (int j = 0; j < 1024; j++)
{
int t=j ^ base[i];
if (XXor[i - 1][j])
{
XXor[i][j] = (XXor[i][j]+XXor[i - 1][j])%MOD;
XXor[i][t] = (XXor[i][t] +XXor[i - 1][j])%MOD;
Xor[i][t] = (Xor[i][t] +XXor[i - 1][j])%MOD;
}
}
}
for (int i = n; i >= 1; i--)
{
And[i][base[i]]++;
for (int j = 0; j < 1024; j++)
{
int t=j & base[i];
if (And[i + 1][j])
{
And[i][j]=(And[i][j]+And[i+1][j])%MOD;
And[i][t] =(And[i][t] + And[i + 1][j])%MOD;
}
}
}
LL ans = 0;
for (int i = 1; i <= n - 1; i++)
for (int j = 0; j < 1024; j++)
if(Xor[i][j] && And[i + 1][j])
ans = (ans + Xor[i][j] * And[i + 1][j])%MOD;
printf("%I64d\n",ans);
}
return 0;
}


  评论这张
 
阅读(39)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017