<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", &t); while (t --) { scanf("%d%d%d", &n, &k, &l); printf("%d\n", sov()); }
}