题目大意

有 $n$ 个小矮人排成一排，每人戴一顶高度不同的帽子（高度为 $1$ 到 $n$ 的排列）。每个小矮人记得某个邻居的帽子高度。给定每个小矮人报告的邻居帽子高度 $h_i$，求有多少种帽子排列方案满足所有报告，答案对 $10^9+7$ 取模。

关键观察

1. 端点约束

• 第一个小矮人只能看到右边邻居（第2个）
• 最后一个小矮人只能看到左边邻居（第$n-1$个）
• 中间的小矮人可能看到左边或右边的邻居

2. 确定性关系

从样例分析可以看出：

• 某些位置的帽子高度可以被唯一确定
• 某些帽子对可以互换位置
• 最终答案通常是 $2^k$ 的形式，其中 $k$ 是可互换的帽子对数

算法思路

步骤1：建立约束图

将问题建模为图：

• 节点：帽子高度 $1$ 到 $n$
• 边：如果某个小矮人报告了邻居的帽子高度，建立对应关系

步骤2：分析确定性约束

1. 端点分析：

   • $h_1$ 必须是第2个小矮人的帽子高度
   • $h_n$ 必须是第$n-1$个小矮人的帽子高度

2. 中间位置分析：

   • 对于位置 $i$ ($2 \leq i \leq n-1$)，$h_i$ 必须是位置 $i-1$ 或 $i+1$ 的帽子高度

步骤3：矛盾检测

如果出现以下情况，答案为 $0$：

• 同一个帽子高度被分配到多个位置
• 约束形成奇数环
• 端点约束冲突

步骤4：组合计数

• 每个确定的约束减少自由度
• 剩余的自由帽子对每对贡献因子 $2$
• 最终答案 = $2^{\text{自由对数}} \bmod (10^9+7)$

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> h(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    
    // 检查端点约束
    if (h[1] == h[n]) {
        cout << 0 << endl;
        return 0;
    }
    
    // 记录每个帽子高度的出现位置
    vector<vector<int>> pos(n + 1);
    for (int i = 1; i <= n; i++) {
        pos[h[i]].push_back(i);
    }
    
    // 分配确定性帽子
    vector<int> cap(n + 1, 0); // cap[i] 表示位置i的帽子高度
    vector<bool> used(n + 1, false); // 记录帽子是否已被使用
    
    // 端点约束
    cap[2] = h[1];
    used[h[1]] = true;
    
    cap[n - 1] = h[n];
    if (used[h[n]]) {
        cout << 0 << endl;
        return 0;
    }
    used[h[n]] = true;
    
    // 处理中间位置
    for (int i = 2; i <= n - 1; i++) {
        // 位置i报告的h[i]必须是i-1或i+1的帽子
        if (cap[i - 1] == 0 && cap[i + 1] == 0) {
            // 两个邻居都未确定，需要进一步分析
            continue;
        } else if (cap[i - 1] == h[i]) {
            // h[i] 是左边邻居的帽子
            if (used[h[i]]) {
                // 帽子已被使用，矛盾
                cout << 0 << endl;
                return 0;
            }
            used[h[i]] = true;
        } else if (cap[i + 1] == h[i]) {
            // h[i] 是右边邻居的帽子
            if (used[h[i]]) {
                cout << 0 << endl;
                return 0;
            }
            used[h[i]] = true;
        } else {
            // 两个邻居都已确定，但都不等于h[i]，矛盾
            if (cap[i - 1] != 0 && cap[i + 1] != 0) {
                cout << 0 << endl;
                return 0;
            }
        }
    }
    
    // 统计自由帽子对
    int free_pairs = 0;
    vector<bool> visited(n + 1, false);
    
    for (int i = 1; i <= n; i++) {
        if (!used[i] && !visited[i]) {
            // 寻找可以配对的帽子
            // 这里需要更复杂的图遍历来找到可互换的帽子对
            // 简化版本：假设每两个未确定的帽子可以形成一对
            visited[i] = true;
            // 在实际实现中，需要构建更完整的约束图
        }
    }
    
    // 简化：假设有k个自由位置，答案为2^(k/2)
    int free_count = 0;
    for (int i = 1; i <= n; i++) {
        if (!used[i]) free_count++;
    }
    
    if (free_count % 2 != 0) {
        cout << 0 << endl;
        return 0;
    }
    
    free_pairs = free_count / 2;
    
    // 计算2^free_pairs mod MOD
    long long result = 1;
    for (int i = 0; i < free_pairs; i++) {
        result = (result * 2) % MOD;
    }
    
    cout << result << endl;
    
    return 0;
}

更完整的实现思路

对于大数据范围 ($n \leq 10^5$)，需要更高效的算法：

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
        h[i]--;
    }
    
    // 构建约束图
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++) {
        if (i > 0) g[i].push_back(h[i]);
        if (i < n - 1) g[i].push_back(h[i]);
    }
    
    // 使用DFS检测连通分量和环
    vector<int> color(n, 0); // 0:未访问, 1:访问中, 2:已访问
    vector<int> comp_size;
    bool has_odd_cycle = false;
    
    function<bool(int, int, int)> dfs = [&](int u, int p, int c) {
        color[u] = c;
        for (int v : g[u]) {
            if (v == p) continue;
            if (color[v] == 0) {
                if (!dfs(v, u, 3 - c)) return false;
            } else if (color[v] == c) {
                return false; // 奇数环
            }
        }
        return true;
    };
    
    long long ans = 1;
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) {
            if (!dfs(i, -1, 1)) {
                ans = 0;
                break;
            }
            // 每个二分图连通分量贡献因子2
            ans = (ans * 2) % MOD;
        }
    }
    
    cout << ans << endl;
    return 0;
}

复杂度分析

• 时间复杂度：$O(n)$，每个节点和边只被访问一次
• 空间复杂度：$O(n)$，存储图和访问状态

样例解析

样例1

输入：5
      3 4 3 4 1
输出：2

解释：

• 位置1报告3 → 位置2帽子=3
• 位置5报告1 → 位置4帽子=1
• 位置2和4都报告4 → 位置3帽子=4
• 剩余帽子2和5可以互换 → $2^1 = 2$ 种方案

总结

本题的关键在于：

1. 将邻居约束转化为图论问题
2. 检测约束一致性（避免矛盾）
3. 统计自由度的组合数

通过图染色检测二分性，每个连通分量贡献因子2，最终得到答案。