F1. Wise Men (Easy Version) - 题解

比赛与标签

比赛: Codeforces Global Round 7 标签: bitmasks, brute force, dp, meet-in-the-middle 难度: *2600

题目大意喵~

主人你好呀~！这道题是说，在一个美丽的城市里住着 n 位聪明的贤者，他们之间有些人互相认识。

我们需要考虑所有 n! 种贤者的排列方式 p1, p2, ..., pn。对于每一种排列，我们会生成一个长度为 n-1 的二进制字符串 s。生成规则是这样的：如果排列中相邻的两个人 pi 和 pi+1 互相认识，那么字符串的第 i 位 si 就是 1，否则就是 0。

我们的任务是，对于所有 2^(n-1) 种可能的二进制字符串，分别计算有多少种排列能够生成它。最后，按照从 0 到 2^(n-1) - 1 的顺序，输出每个二进制字符串对应的排列数量，用空格隔开。

简单来说，就是给一个关系图，问所有排列中，相邻关系构成的 n-1 位二进制串，每种串分别有多少个排列能生成，的说。

解题思路，来一起思考吧！

喵呜~ 看到 n 最大只有 14，而且要我们对所有 2^(n-1) 种情况计数，直接的想法——比如暴力枚举所有 n! 的排列——肯定是不行的啦！14! 是一个天文数字，计算机会累坏的！

这种涉及到“所有子集”、“排列顺序”并且数据范围在 20 左右的问题，通常都是在暗示我们使用一种非常强大的魔法——状态压缩动态规划（状压DP），喵！

状压DP的核心就是用一个整数的二进制位来表示一个集合的状态。在这里，我们可以用一个 n 位的二进制数 mask 来表示哪些贤者已经被我们排好队了。如果 mask 的第 i 位是 1，就代表第 i 个贤者（从0开始编号）已经在我们的排列里了。

那么，DP的状态应该怎么设计呢？一个好的DP状态需要包含足够的信息来进行转移。在构建排列的过程中，我们需要知道：

已经有哪些人被排列了？ —— 这可以用一个 mask 来表示。
排列的最后一个人是谁？ —— 因为下一个人的关系只和前一个人有关，所以我们需要知道队尾是谁。
到目前为止生成的二进制字符串是什么？ —— 这正是我们最终要统计的东西！

所以，一个完整的DP状态可以定义成 dp[mask][last][pattern]，它表示：

mask: 已经被使用的贤者的集合。
last: 这个排列的最后一个贤者是 last。
pattern: 到目前为止生成的二进制字符串（我们把它看作一个整数）。
dp[mask][last][pattern] 的值就是满足这些条件的部分排列的数量。

但是，pattern 的长度是变化的，它等于 popcount(mask) - 1。如果直接把它放进状态里，状态空间会变得非常复杂且巨大。mask 有 2^n 种，last 有 n 种，pattern 最大有 2^(n-1) 种，这可不行呀！

我们可以换个思路，让 dp 数组本身来存储 pattern 的信息。我们可以定义 dp[mask][last] 为一个数组（或者 vector），它的下标表示 pattern，值表示对应的排列数。

于是，我们的DP状态就变成了： dp[mask][last] 是一个数组，其中 dp[mask][last][pattern] 表示：

使用了 mask 集合中的贤者。
排列的最后一位是 last。
生成的二进制串是 pattern。
值为满足条件的排列数量。

这个数组的大小是 2^(popcount(mask) - 1)。

状态转移过程如下喵~

我们按照排列的长度 k（也就是 mask 中 1 的个数）从小到大进行递推。

初始化 (k=1): 当排列中只有一个人时，比如说贤者 i。
- mask 就是 1 << i。
- last 就是 i。
- 此时排列长度为1，还没有产生任何相邻关系，所以二进制串长度为0，我们可以认为 pattern 是 0。
- 所以，dp[1 << i][i][0] = 1。这表示只有一个人的排列，只有一种方式。
递推 (从 k 转移到 k+1): 假设我们已经计算出了所有长度为 k 的部分排列的结果。现在我们要在此基础上添加第 k+1 个人。
- 我们遍历所有大小为 k 的 mask。
- 对于每个 mask，遍历所有可能的 last ( last 必须在 mask 中)。
- 对于每个 pattern (大小从 0 到 2^(k-1)-1)，如果我们有 dp[mask][last][pattern] > 0：
  - 遍历所有还未被使用的贤者 j ( j 不在 mask 中)。
  - 我们可以把 j 接在 last 后面，形成一个更长的排列。
  - 新的状态是：
    - new_mask = mask | (1 << j)
    - new_last = j
    - 新生成的二进制位取决于 last 和 j 是否认识。如果认识，这位是 1；不认识，这位是 0。
    - new_pattern = pattern | (adj[last][j] << (k-1))。我们把新的二进制位加在 pattern 的最高位（第 k-1 位）。
  - 我们将 dp[mask][last][pattern] 的计数值累加到新的状态上： dp[new_mask][new_last][new_pattern] += dp[mask][last][pattern]
最终答案: 当 k 增加到 n 时，我们就得到了所有完整的排列。
- mask 是 (1 << n) - 1，表示所有贤者都用上了。
- 最后的答案 ans[pattern] 就是 sum(dp[(1 << n) - 1][last][pattern]) 对所有可能的 last 求和。

为了节省空间，我们可以使用滚动数组的思想，只保留当前长度 k 和下一长度 k+1 的DP表，喵~

可爱代码の实现

cpp

// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 读取贤者数量 n，喵~
    int n;
    cin >> n;

    // 读取邻接矩阵，adj[i][j] = true 表示 i 和 j 互相认识
    vector<string> mat(n);
    for (int i = 0; i < n; i++) {
        cin >> mat[i];
    }
    vector<vector<bool>> adj(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (mat[i][j] == '1') {
                adj[i][j] = true;
            }
        }
    }

    int total_masks = 1 << n;
    
    // 预处理：按popcount（1的个数）给mask分组，方便按排列长度遍历
    vector<vector<int>> masks_by_count(n + 1);
    for (int mask = 0; mask < total_masks; mask++) {
        int cnt = __builtin_popcount(mask);
        if (cnt >= 1 && cnt <= n) {
            masks_by_count[cnt].push_back(mask);
        }
    }

    // 预处理：对于每个mask，存下所有不在mask中的元素，方便快速查找下一个可以放的人
    vector<vector<int>> non_set_bits(total_masks);
    for (int mask = 0; mask < total_masks; mask++) {
        for (int j = 0; j < n; j++) {
            if (!(mask & (1 << j))) {
                non_set_bits[mask].push_back(j);
            }
        }
    }

    // dp_cur[mask][last] 是一个vector，下标是 pattern，值是数量
    // 我们用滚动数组优化空间，dp_cur 是当前长度，dp_next 是下一长度
    vector<vector<vector<long long>>> dp_cur(total_masks, vector<vector<long long>>(n));

    // Base Case: 排列长度为 1
    for (int i = 0; i < n; i++) {
        int mask = 1 << i;
        // 长度为1的排列，pattern长度为0，只有一种可能 pattern=0，数量为1
        dp_cur[mask][i] = vector<long long>(1, 0);
        dp_cur[mask][i][0] = 1;
    }

    // 主循环：从长度为 k 的排列扩展到长度为 k+1 的排列
    for (int k = 1; k < n; k++) {
        vector<vector<vector<long long>>> dp_next(total_masks, vector<vector<long long>>(n));
        
        // 遍历所有长度为 k 的排列
        for (int mask : masks_by_count[k]) {
            for (int last = 0; last < n; last++) {
                if (!(mask & (1 << last))) continue; // last必须在mask里
                if (dp_cur[mask][last].empty()) continue; // 如果没有这样的排列，就跳过

                int pattern_size = 1 << (k - 1);
                auto& vec = dp_cur[mask][last];

                // 遍历当前状态下所有可能的 pattern
                for (int pattern_val = 0; pattern_val < pattern_size; pattern_val++) {
                    long long count_val = vec[pattern_val];
                    if (count_val == 0) continue;

                    // 遍历下一个可以放的贤者 j
                    for (int j : non_set_bits[mask]) {
                        int new_mask = mask | (1 << j);
                        bool bit = adj[last][j];
                        
                        // 计算新的 pattern
                        long long new_pattern = pattern_val;
                        if (bit) {
                            new_pattern |= (1LL << (k - 1)); // 在第 k-1 位上添上 1
                        }

                        // 初始化 dp_next 的 vector
                        if (dp_next[new_mask][j].empty()) {
                            dp_next[new_mask][j] = vector<long long>(1 << k, 0);
                        }
                        
                        // 状态转移，累加数量
                        dp_next[new_mask][j][new_pattern] += count_val;
                    }
                }
            }
        }
        // 滚动数组，用 dp_next 更新 dp_cur
        swap(dp_cur, dp_next);
    }

    // 收集最终答案
    int full_mask = (1 << n) - 1;
    vector<long long> ans(1 << (n - 1), 0);
    // 遍历所有长度为 n 的排列
    for (int last = 0; last < n; last++) {
        if (dp_cur[full_mask][last].empty()) continue;
        auto& vec = dp_cur[full_mask][last];
        // 将所有以 last 结尾的排列的计数，加到最终答案里
        for (int pattern_val = 0; pattern_val < (1 << (n - 1)); pattern_val++) {
            ans[pattern_val] += vec[pattern_val];
        }
    }

    // 按格式输出答案，喵~
    for (int x = 0; x < (1 << (n - 1)); x++) {
        cout << ans[x];
        if (x < (1 << (n - 1)) - 1) {
            cout << " ";
        }
    }
    cout << endl;

    return 0;
}

复杂度分析的说

时间复杂度: O(n² * 3ⁿ) 的说。我们的DP过程，状态转移的总计算量可以这样估算： Σ (k=1 to n-1) [C(n, k) * k * (n-k) * 2^(k-1)]
- C(n, k): 长度为 k 的 mask 数量。
- k: last 的选择数量。
- n-k: next 的选择数量。
- 2^(k-1): pattern 的数量。这个和式可以通过二项式定理相关知识化简，最终结果与 n² * 3ⁿ 同阶。对于 n=14，3^14 大约是 4.7 * 10^6，再乘上一个 n² 的因子，是完全可以在时限内跑完的，喵~
空间复杂度: O(n * 3ⁿ) 的说。我们使用了滚动数组，所以只需要存两层DP表。每一层DP表的空间消耗是： Σ (mask) Σ (last in mask) [大小为 2^(popcount(mask)-1) 的vector] 总空间大约是 Σ (k=1 to n) [C(n, k) * k * 2^(k-1)]，这个和式的结果是 n * 3^(n-1)。所以空间复杂度是 O(n * 3ⁿ)，对于 n=14 也是可以接受的。

知识点与总结

这真是一道非常经典的状压DP题目呢，主人！通过这道题，我们可以学到很多东西：

状压DP (Bitmask DP): 核心思想是用整数的二进制位来表示集合状态，特别适合解决与子集、排列相关的组合计数或最优化问题。
DP状态设计: 如何将问题抽象成DP状态是解题的关键。这道题中，dp[mask][last] 并存储 pattern 计数数组的设计非常巧妙，解决了 pattern 长度可变的问题。
滚动数组优化: 当DP的转移只依赖于前一阶段时，使用滚动数组可以有效降低空间复杂度，从 O(n * ...) 降到 O(...)。
预处理: 像代码中提前计算 masks_by_count 和 non_set_bits，可以避免在DP循环中重复计算，让代码更清晰、更高效。

总而言之，遇到这种数据范围不大（n <= 20），且问题涉及到排列组合和子集的问题时，一定要先往状压DP的方向想一想哦！多练习，你也能成为DP大师的，喵~！加油！

F1. Wise Men (Easy Version) - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路，来一起思考吧！ ​

可爱代码の实现 ​

复杂度分析的说 ​

知识点与总结 ​