一旦选择，便无法回头

· · 题解

题目链接

简要题面：

有一个无向图（可能不连通），n 个点，m 条边。两个不同点的编号之差不大于 K。任意一个点的度数都为偶数（有无度数的点）。对这个无向图的形态进行计数，模 10^9 + 7。

## 思路： 状压 $\texttt{DP}$，计数。很好想的。这一类题的难点其实在不重不漏。 $\texttt{DP}$ 题都是要看性质的。题面其实提示的很清楚了：“任意一个点的度数都为偶数”。显然，出题人希望你通过点的度数的奇偶来推无向图的形态。所以无脑设这题的状态是 $f_{i,j,k}$ 表示 $i$ 个点，$j$ 条边，$k$ 是每个点度数的奇偶（$1$ 是奇数，$0$ 是偶数）。 边界呢？因为当 $i=1$ 时是没有意义的，所以 $i$ 是要从 $2$ 开始的，$1 \to f_{2,0,0}$。 枚举范围呢？“两个不同点的编号之差不大于 $K$”，这句话启示我们让$i-K \sim i-1$ 号点转移到 $i$ 号点。 第 $i$ 位是当前结点，所以每一加一条边度数都会改变，所以 $k \oplus 1 \to k$（状态正着存）。然后改变另一个点的奇偶，即 $k \oplus (2^{i-c}) \to k$（$c$ 为与 $i$ 连边的点）。 可以发现，这样的转移是有序的，每次都由编号大的结点指向编号小的结点。 于是有转移方程： $f_{i,j,k} = \sum^{i-1}_{c = i-K} {\sum^{2^{K+1}-1}_{a=0}}f_{i,j-1,k \oplus 1 \oplus 2^{i-c}}

于是某个大聪明打出了这样的代码：

signed main() {
    cin >> n >> m >> k;
    dp[2][0][0] = 1;
    for (int i = 2; i <= n; i++) {
        for (int change = max(1, i - k); change <= i - 1; change++) {
            for (int j = 1; j <= m; j++) {
                for (int now_state = 0; now_state < (1 << (k + 1)); now_state++) {
                    dp[i][j][now_state] = (dp[i][j][now_state] + dp[i][j - 1][now_state ^ 1 ^ (1 << i - change)]) % mod;
                }
            }
        }
    }
    cout<<dp[n][m][0]<<'\n';
    return 0;
}

诶，怎么不对呢？怎么都输出 0 啊。形如这样的情况，说明漏了转移。

我们观察到，每一次多一个点的情况都要转移过去，这也是没有讨论全面的一个错误。

添加一个发送式转移至下个阶段：

f_{i+1,j,k \times 2^{1}} = \sum ^{m}_{j=0} \sum^{2^K-1}_{k = 0}f_{i,j,k}

坑点：位运算要打括号！取模要小心！

Code:

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int Data_Range_Of_N = 30 + 5;
const int Data_Range_Of_K = 10 + 5;
int n, m, k;
int dp[Data_Range_Of_N][Data_Range_Of_N][1 << Data_Range_Of_K];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    dp[2][0][0] = 1;
    for (int i = 2; i <= n; i++) {
        for (int change = max(1, i - k); change <= i - 1; change++) {
            for (int j = 1; j <= m; j++) {
                for (int now_state = 0; now_state < (1 << (k + 1)); now_state++) {
                    dp[i][j][now_state] = (dp[i][j][now_state] + dp[i][j - 1][now_state ^ 1 ^ (1 << i - change)]) % mod;
                }
            }
        }
        for(int j = 0;j<=m;j++) {
            for(int now_state = 0;now_state < (1 << k);now_state++) {
                dp[i+1][j][now_state << 1] = (dp[i][j][now_state] + dp[i+1][j][now_state << 1]) % mod;
            }
        }
    }
    cout<<dp[n][m][0]<<'\n';
    return 0;
}