題目:
http://acm.hdu.edu.cn/showproblem.php?pid=5119
題意:
給出n個數字,求他們的中任意挑出一些數字(可以是0個)異或之後的結果大于等于m的方法數。
思路:
最多40個數,數字最大1e6可以暴力dp得出結果,dp[i][j]表示放入i個數字時異或結果為j的方法數,可以用滾動數組來優化記憶體,然後注意初始化,暴力就過了。
代碼:
#define N 1123456
long long n,m;
long long flag,sum,ave,ans,res,len,ans1,ans2;
long long a[50],dp[2][N];
int main()
{
long long i,j,k,kk,t,x,y,z;
scanf("%lld",&k);
kk=0;
while(k--)
{
scanf("%lld%lld",&n,&m);
res=0;
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);res=max(res,a[i]);
}
memset(dp,0,sizeof(dp));
dp[1][0]=1;
for(i=1;i<=n;i++)
{
for(j=0;j<=MAX;j++)
dp[(i+1)%2][j]=dp[i%2][j];
for(j=0;j<=MAX;j++)
dp[(i+1)%2][a[i]^j]+=dp[i%2][j];
}
sum=0;
for(i=m;i<=MAX;i++)
sum+=dp[(n+1)%2][i];
printf("Case #%lld: %lld\n",++kk,sum);
}
return 0;
}