题目：

pid=1189" target="_blank">nyoj 1189 yougth和他的朋友们

这题目是14年北京赛区的原题。讲题的时候说有三种解法，我们是用dp做的当时。原题目链接：Happy Matt Friends

题意就不在说了。由于要求的是满足条件的种数。

我们定义状态dp【i】【j】：当我们把第 i 个数放进去之后得到 j 的种数是多少

那么我们能够得到状态转移方程：dp【i】【j^ a [ i ] 】 += dp【i-1】【j】

就是当前得到每一个 j ^  a [ i ] 有前 i-1 个数得到。整个dp一遍就是得到结果了。

还有注意这里数组比較大。直接开的话会超内存，所以要用滚动数组优化。

AC代码：

#include <cstring>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <queue>

#include <vector>

#include <map>

using namespace std;

typedef long long LL;

const int N = 1100100;

LL dp[3][N];

int a[50];

int main()

{

    int n,m;

    while(~scanf("%d%d",&n,&m))

    {

        memset(dp,0,sizeof(dp));

        int ma = 0;

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&a[i]);

            if(a[i]>ma)

                ma = a[i];

        }

        dp[0][0] = 1;

        for(int i=1;i<=n;i++)

        {

            memset(dp[i%2],0,sizeof(dp[i%2]));

            for(int j=0;j<=ma;j++)

            {

                dp[i%2][j^a[i]] += dp[(i+1)%2][j];

                dp[i%2][j] += dp[(i+1)%2][j];

                if((j^a[i])>ma)

                    ma = (j^a[i]);

            }

        }

        LL  ans = 0;

        for(int i=m;i<=ma;i++)

            ans+=dp[n%2][i];

        printf("%lld\n",ans);

    }

    return 0;

}