【BZOJ3866】The Romantic Hero DP(示例代码)

CQzhangyu 2020-10-06

栏目: Web ·

来源: CQzhangyu

作者:CQzhangyu

简介  这篇文章主要介绍了【BZOJ3866】The Romantic Hero DP(示例代码)以及相关的经验技巧,文章约1620字,浏览量293,点赞数1,值得参考!

【BZOJ3866】The Romantic Hero

题意:一个序列,从中选取两个子序列S和T,满足S中所有元素都在T左边,并且S中所有数的xor和=T中所有数的and和,求方案数。n<=1000,ai<1024

题解:用s[i][j]表示从1-i中选出一些数,最后一个数是i,xor和为j的方案数。转移时用前缀和优化即可。用t[i][j]表示从i-n中选出一些数,最左边的数是i,and和为j的方案数,转移同理。计算答案的时候,用t[i][j]*s[1...i-1][j]即可。

 

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int P=1000000007;
typedef long long ll;
int n;
ll ans;
int ss[1010][1050],s[1050],t[1050],st[1010][1050],v[1010];
inline int rd()
{
	int ret=0,f=1;	char gc=getchar();
	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}
	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();
	return ret*f;
}
void work()
{
	n=rd(),ans=0;
	int i,j;
	for(i=1;i<=n;i++)	v[i]=rd();
	memset(ss,0,sizeof(ss)),memset(st,0,sizeof(st));
	for(i=1;i<=n;i++)
	{
		memset(s,0,sizeof(s)),s[v[i]]=1;
		for(j=0;j<1024;j++)	s[j^v[i]]=(s[j^v[i]]+ss[i-1][j])%P;
		for(j=0;j<1024;j++)	ss[i][j]=(ss[i-1][j]+s[j])%P;
	}
	for(i=n;i>=1;i--)
	{
		memset(t,0,sizeof(t)),t[v[i]]=1;
		for(j=0;j<1024;j++)	t[j&v[i]]=(t[j&v[i]]+st[i+1][j])%P;
		for(j=0;j<1024;j++)	ans=(ans+(ll)ss[i-1][j]*t[j])%P,st[i][j]=(st[i+1][j]+t[j])%P;
	}
	printf("%lld\n",ans);
}
int main()
{
	int T=rd();
	while(T--)	work();
	return 0;
}//2 3 1 2 3 4 1 2 3 3

 


以上就是本文的全部内容,希望对大家的学习有所帮助,本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 原文地址:http://www.cnblogs.com/CQzhangyu/p/7501166.html

相关文章

hdu 4901 The Romantic Hero 计数dp,位计算(示例代码)

HDU - 4901 The Romantic Hero(dp)(示例代码)

Error from server (NotFound): the server could not find the requested resource (get services http:he

he last packet sent successfully to the server was 0 milliseconds ago. The driver has not received a

J - Romantic(示例代码)

romantic(示例代码)

powershell 来自https://stackoverflow.com/questions/5466329/whats-the-best-way-to-determine-the-locatio

hdu_2669 Romantic(扩展欧几里得)(示例代码)