<div class="post_brief"><p>
立杰出的题，orz。</p>

 

一个时间比较微妙的状压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", &amp;t);
while (t --) {
	scanf("%d%d%d", &amp;n, &amp;k, &amp;l);
	printf("%d\n", sov());
}



}