题解

思路概述

• 将 $2^n$ 个灯状态视为 $n$ 维超立方体 $Q_n$ 的顶点，相邻状态之间连边。若在计划 $g$ 中，把所有被映射为数字 $x$ 的状态集合记为 $S_x$，则小修拿到 $x$ 时，只要当前状态距离 $S_x$ 至多 1，就能通过翻动 0/1 盏灯把局面引导到 $S_x$ 上。因此 $S_x$ 必须是 $Q_n$ 的支配集（dominating set），题目要求把顶点划分成 $m$ 个支配集，即 domatic 分割问题。
• 超立方体是 $n$ 正则图，理论上 domatic 数不超过 $n+1$。当 $n=2^k-1$ 时，存在经典的 1-完美码（Hamming 码）能恰好达到该上界，把 $Q_n$ 分成 $n+1=2^k$ 个互不相交的支配集。对应地，若我们把状态 $s\in\{0,1\}^n$ 看成列向量，预先构造 $k\times n$ 的 Hamming 矩阵 $H$（第 $j$ 列为 $j$ 的 $k$ 位二进制表示），则综合征 $H\cdot s$（模 2）唯一确定所在的支配集。
• 小修拿到数字 $x$ 时，把 $x$ 写成 $k$ 位二进制即目标综合征 $t$，当前状态综合征为 $c$。若 $c=t$，不翻灯即可；否则差值 $d=c\oplus t$ 必然等于 $H$ 的某一列，翻动对应的那盏灯即可把综合征改成 $t$，使得 $g(s)=x$。
• 当 $n$ 不是 $2^k-1$ 时，取满足 $2^k-1\le n$ 的最大 $k$，仅对前 $2^k-1$ 盏灯使用 Hamming 码，其余灯保持不动即可。若 $m\le 2^k$，可把未用的综合征合并映射到 $[0,m-1]$；若 $m>2^k$，严格划分不存在，只能在此基础上做启发式拆分以求部分分数。

输出实现要点

• 构造 Hamming 矩阵 $H$，对所有状态 $s$ 枚举整数 $0\le mask<2^n$，把 $mask$ 的二进制作为列向量，即可算出综合征并进行映射。
• 若 $m<2^k$，可以把多余的综合征按任意方式合并，例如直接对综合征取模 $m$；若恰好等于 $2^k$，直接输出综合征对应的十进制即可。
• 可选地对所有 $(x,s_0)$ 模拟一次验证：从 $s_0$ 计算综合征并尝试翻灯，确认能得到 $x$，以保证答案合法。

参考实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, p;
    if (!(cin >> n >> m >> p)) return 0;
    int k = 0;
    while ((1 << k) - 1 <= n) ++k;
    if ((1 << k) - 1 > n) --k;
    int core = (1 << k) - 1;
    vector<int> col(k);
    vector<int> ans(1 << n);
    for (int mask = 0; mask < (1 << n); ++mask) {
        int code = 0;
        for (int j = 0; j < core; ++j) {
            if (mask >> j & 1) {
                int idx = j + 1;
                for (int bit = 0; bit < k; ++bit)
                    if (idx >> bit & 1) code ^= 1 << bit;
            }
        }
        if (k == 0) code = 0;
        ans[mask] = (k == 0 ? 0 : (code % m));
    }
    for (int i = 0; i < (1 << n); ++i) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    return 0;
}

该程序首先确定最大的 Hamming 码维数 k，然后按综合征分组输出决策表。若 m > 2^k，则需要进一步对综合征进行拆分或引入其他启发式以提升得分。上述构造在 m ≤ 2^k 时可保证对任意初始状态和目标数字都能在翻动至多一盏灯的前提下实现正确猜测。