Codeforces #191 Div2. E. Axis Walking

Eもいまいち出題意図がよくわからない問題。
http://codeforces.com/contest/327/problem/E

問題

N個の自然数配列Aがある。総和をDとする。

1～NのpermutationをPとしたとき、i番目のステップではA[P[i]]マスだけ前進するとする。
当然、この組み合わせはN!通りでいずれも最後はDマス前進する。

ここで、K種類のマス番号が与えられる。
これらのマスで止まらずにDマス進むPの組み合わせ数を答えよ。

解法

N<=24なのでBitDPで処理する。
N個のうちに利用したA中要素をBitDPで処理し、途中K個のマスに含まれる場合は組み合わせ数を0、それ以外は今見ているbitmapから1つbitを除いた時の組み合わせ数を加算していけばよい。

int N,K;
ll A[30],B[3];
vector<int> BM[2];
ll comb[30][30];

ll mo=1000000007;
ll DP[1<<25];

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	
	N=GETi();
	j=0;
	FOR(i,N) j+=A[i]=GETi();
	K=GETi();
	FOR(i,K) B[i]=GETi();
	
	DP[0]=1;
	for(i=1;i<1<<N;i++) {
		ll tot=0;
		FOR(j,N) if(i&(1<<j)) {
			tot+=A[j];
			DP[i]+=DP[i^(1<<j)];
		}
		DP[i]%=mo;
		if(K>=1 && tot==B[0]) DP[i]=0;
		if(K>=2 && tot==B[1]) DP[i]=0;
	}
	cout << DP[(1<<N)-1] << endl;
}

まとめ

Eの割に短く書ける問題。