「NOIP 模拟赛」篮球比赛2

题目大意：你需要在一个长度为 $n$ 的空数组上填数，每个数的范围是 $[0,l]$，并且要满足这 $n$ 个数的某个集合的和是 $k$，问有多少种填数方案。$n,k \leq 20$

状压DP，$f[i][j]$ 表示前 $i$ 个数能表示的数的状态是 $j$ 的方案数，其中 $j$ 是一个 $k$ 位的二进制数，每一位表示该数是否能表示。

#include <cstdio>

const int N = 25, M = 1048580, XZY = 1e9 + 7;
int f[N][M], n, k, l, m, ans;

int main() {
    freopen("basketball2.in", "r", stdin);
    freopen("basketball2.out", "w", stdout);

    scanf("%d%d%d", &n, &k, &l);
    m = (1 << k) - 1;
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) { //前i个数
        if (l > k) for (int j = 0; j <= m; ++j) //前i-1个数能取到的状态
            f[i][j] = 1LL * f[i-1][j] * (l - k) % XZY; //x>k
        for (int j = 0; j <= m; ++j) {
            (f[i][j] += f[i-1][j]) %= XZY; //x=0
            if (f[i-1][j]) for (int x = 1; x <= k && x <= l; ++x) //注意x要同时小于k和l
                (f[i][(j|(j<<x)|(1<<x-1))&m] += f[i-1][j]) %= XZY; //1<=x<=k
        }
    }
    for (int i = 0; i <= m; ++i)
        if (i >> k - 1 & 1) (ans += f[n][i]) %= XZY;
    printf("%d\n", ans);

    fclose(stdin);
    fclose(stdout);
    return 0;
}