「JXOI 2012」奇怪的道路

题目大意：

$f[i][j][k]$ 表示前 $i$ 个点用了 $j$ 条边，$[i-k,i]$ 的点的度数奇偶性状态为 $k$，且 $i-k$ 之前的点保证合法的方案数。

注意向第 $i-k+l-1$ 个点连边要优先枚举，因为优化掉了第四维，不然就会出现连边顺序不同导致的方案数增加。

#include <cstdio>
 
const int mod = 1000000007;
int f[31][31][512], n, m, K;
 
int main() {
    scanf("%d %d %d", &n, &m, &K);
    f[0][0][0] = 1;
    for (int i = 1; i <= n; ++i) { //前i个点
        for (int j = 0; j <= m; ++j) //连了j条边
            for (int k = 0; k < 1 << K; ++k) //点i不连边
                f[i][j][k<<1] = f[i-1][j][k];
        for (int l = 1; l <= K && l < i; ++l) //点i向第i-k+l-1个点连边
            for (int j = 0; j < m; ++j) //目前连了j条边
                for (int k = 0; k < 1 << K + 1; ++k)
                    (f[i][j+1][k^1^(1<<l)] += f[i][j][k]) %= mod; //多连一条边
    }
    printf("%d\n", f[n][m][0]);
    return 0;
}

时间复杂度 $O(2^{k+1}nmk)$