HDU 5119 Happy Matt Friends(2014 베이징 지역 경기 라이브 경기 H 문제 누드 백팩 DP)

비록 하나의 간단한 DP이지만, 심지어는 그룹을 굴리지 않아도 AC를 할 수 있어 데이터 양이 그리 크지 않다.
N개의 수에 대해, 각각의 수는 두 개의 상태만 존재하며, 취하거나 취하지 않는다.
상태 전환 방정식을 쉽게 찾아낼 수 있습니다.

dp[i][j] = dp[i - 1][j ^ a[i]] + dp[i - 1][j];

dp[i][j]의 뜻은 수열의 앞 i개의 숫자에 대해 XOR와 j의 방안 수를
상태 이동 방정식의 dp[i-1][j]는 현재 이 숫자를 찾지 않음을 의미하고, dp[i-1][j^a[i]]는 현재 이 숫자를 찾으려는 것을 의미한다.
 
이 문제는 그래도 잘 이해해야 해!
source code :

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler

#include <stdio.h>

#include <iostream>

#include <cstring>

#include <cmath>

#include <stack>

#include <queue>

#include <vector>

#include <algorithm>

#define ll long long

#define Max(a,b) (((a) > (b)) ? (a) : (b))

#define Min(a,b) (((a) < (b)) ? (a) : (b))

#define Abs(x) (((x) > 0) ? (x) : (-(x)))



using namespace std;



const int INF = 0x3f3f3f3f;



int dp[2][1 << 20];

int a[41];



int main(){

    int i, j, k, T, n, m, numCase = 0;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&m);

        for(i = 1; i <= n; ++i) scanf("%d", a + i);

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

        dp[0][0] = 1;

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

            for(j = 0; j < (1 << 20); ++j){

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

            }

        }

        long long ans = 0;

        for(i = m; i < (1 << 20); ++i){

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

        }

        printf("Case #%d: %I64d
",++numCase, ans);

    }

    return 0;

}