BZOJ3870 Our happy ending

立杰出的题，orz。

一个时间比较微妙的状压DP。用一个二进制状态表示0~k中哪些数已经可以被表示出来了，然后大于k的数直接乘，因为对状态不产生影响。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define pow2(x) (1<<(x))
#define _l (long long int)

const int maxn = 21;
const int maxb = pow2(maxn) + 9;
const int mod = 1e9 + 7;

int n, k, l, f[2][maxb], zu, va;

#define incm(_a_,_b_) { \
	_a_ +=  _b_; \
	if (_a_ >= mod) \
		_a_ %= mod; \
}

int sov() {
	int prv(0), cur(1);
	memset(f, 0, sizeof(f));
	va = max(0, l - k) + 1;
	zu = pow2(k + 1) - 1;
	f[cur][1] = 1;
	for (int ti = 0; ti < n; ++ ti) {
		swap(cur, prv);
		for (int i = zu; i; -- i)
			f[cur][i] = 0;
		for (int i = zu; i; -- i)
			if (f[prv][i]) {
				for (int j = 1; j <= k; ++ j) {
					int zn((i | (i << j)) & zu);
					incm(f[cur][zn], f[prv][i]);
				}
				incm(f[cur][i], _l f[prv][i] * va % mod);
			}
	}
	int ans(0);
	for (int i = zu, e = pow2(k); i >= e; -- i)
		incm(ans, f[cur][i]);
	return ans;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	int t;
	scanf("%d", &t);
	while (t --) {
		scanf("%d%d%d", &n, &k, &l);
		printf("%d\n", sov());
	}
}