首页 > 代码库 > hdu5119(dp)

hdu5119(dp)

 

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5119

 

分析:dp[i][j]表示由前i个数组成异或和为j的方法数,则dp[i][j]=d[i-1][j^a[i]]+dp[i][j];

        边界:dp[0][0]=1,其他为0;复杂度40*1e6

 

 

#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define inf 1<<30#define mod 1000000007using namespace std;int a[100];int dp[2][(1<<20)];int main(){    int T,n,m;    int cas=1;    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&n,&m);        memset(dp,0,sizeof(dp));        for(int i=1; i<=n; i++)scanf("%d",&a[i]);        int pre=0,cur=1;        dp[0][0]=1;        for(int i=1; i<=n; i++)        {             memcpy(dp[cur],dp[pre],sizeof(dp[pre]));//小于i个数异或和为j的方法要赋值给现在            for(int j=0; j<=(1<<20)-1; j++)            {                int num=j^a[i];                if(dp[pre][num])                {                    dp[cur][j]+=dp[pre][num];                }            }            swap(pre,cur);        }        LL ans=0;        for(int i=m; i<=(1<<20)-1; i++)ans+=dp[pre][i];        printf("Case #%d: ",cas++);        printf("%I64d\n",ans);    }}
View Code

 

hdu5119(dp)