SRM 605 AlienAndSetDiv1

http://community.topcoder.com/stat?c=problem_statement&pm=12980&rd=15838
http://apps.topcoder.com/wiki/display/tc/SRM+605

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;

static const int MOD = 1000000007,  MAX_N = 50, MAX_K = 10;
int k;
int dp[2*MAX_N+1][2*MAX_N+1][1<<(MAX_K-1)];

class AlienAndSetDiv1 {
	public:
	int getNumber(int N, int K) {
		k=K;
		memset(dp,-1,sizeof(dp));
		return rec(2*N, 0, 0);
	}

	int rec(int n, int g, int mask){
		if(dp[n][g][mask]!=-1)return dp[n][g][mask];
		long res=0;
		if(n==0){
			res= g==0 && mask==0 ? 1 : 0;
		}else if(mask==0 && g==0){
			if(k==1)res=2*rec(n-1,1,0);
			else res=2*rec(n-1,0,1);
		}else{
			if(g>0){
				int nmask=mask<<1;
				int ng=g-1;
				if(nmask&(1<<(k-1))){
					nmask^=(1<<(k-1));
					ng++;
				}
				res=rec(n-1,ng,nmask);
			}
			int nmask=(mask<<1)|1;
			int ng=g;
			if(nmask&(1<<(k-1))){
				nmask^=(1<<(k-1));
				ng++;
			}
			res+=rec(n-1,ng,nmask);
		}
		res%=MOD;
		return dp[n][g][mask]=res;
	}

};

コードはEditorialsのパクリ
Aを基準に考えられていて、g=Aに入れた数-Bに入れた数みたいな感じで、if(g>0)の部分がBに入れる処理になってて、maskが1<<(k-1)を超える前のAに入れたbit(ワカリニクイ)
maskは、if(g>0)の部分では足されてない、1<<(k-1)を超えた場合はgが足される(Kを超えたのでBに入れられる)
K=5のとき
mask=001111
↓左にビットシフトして
mask=011110
mask&(1<<(k-1))=true

g++;
mask=001110 (右から5番目のbitが0になる)
みたいにdfsしてる。

なんとなくわかったけど、類似問、解くのきつそー。