Codeforces #297 Div2 E. Anya and Cubes

Dに比べるとオーソドックスな問題か。
http://codeforces.com/contest/525/problem/E

問題

N要素の数列A[i]が与えられる。
これらA[i]個の整数の和を取る際、最大K箇所A[i]の直後に階乗記号の"!"を付与することができる。

A[i](に一部階乗記号を付けたもの)の和がSになるような階乗記号のつけ方の組み合わせを求めよ。

解法

Nは最大25とさほど大きくない。
よって半分全列挙を行い、

• Aの前半半分のうちx回階乗記号を使って総和がTとなる組み合わせP(x,T)
• Aの後半半分のうちy回階乗記号を使って総和がUとなる組み合わせQ(y,U)

をDPで求める。

あとは各P(x,T)に対し、Q(y,S-T)を0≦y≦K-xの範囲で求めて足し合わせればよい。

int N,K;
ll S,A[40];
ll B[100];

map<ll,ll> M[2][30];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	FOR(i,N) cin>>A[i];
	B[0]=1;
	FOR(i,20) {
		B[i+1]=B[i]*(i+1);
		if(B[i]==-1 || B[i+1]>10000000000000000LL) B[i+1]=-1;
	}
	
	M[0][0][0]=M[1][0][0]=1;
	FOR(i,N) {
		int id=i<12;
		map<ll,ll> tmp[16];
		FOR(x,15) tmp[x]=M[id][x];
		FOR(x,15) {
			FORR(r,tmp[x]) {
				M[id][x][r.first+A[i]] += r.second;
				if(A[i]<=18 && r.first+B[A[i]]<=S) M[id][x+1][r.first+B[A[i]]] += r.second;
			}
		}
	}
	
	ll ret=0;
	FOR(x,15) FOR(y,15) if(x+y<=K) {
		FORR(r,M[0][x]) ret += r.second * M[1][y][S-r.first];
	}
	cout<<ret<<endl;
}

まとめ

Nが奇数のため半分全列挙が若干思い浮かびにくいね。