题解思路

本题的核心是通过最少的交互次数（调用Encode函数），还原双射加密函数f的逆映射f'（即解密映射）。关键思路是二进制分组查询，利用二进制表示的唯一性，通过log2(n)次查询即可确定所有元素的逆映射，完美匹配题目中T的约束（如n=1e5时仅需17次查询）。

核心原理

1. 双射特性：加密函数f是[1,n]到[1,n]的双射，因此f(x)与x一一对应，f(S)（集合S的加密结果）与S也一一对应。
2. 二进制分组：每个整数x的二进制表示是唯一的。对于二进制的每一位k（从0开始），构造集合S_k（包含所有第k位为1的x），调用Encode(S_k)得到S'_k = f(S_k)。
3. 逆映射推导：对于加密后的元素y = f(x)，y属于S'_k当且仅当x的第k位为1。通过所有位的S'_k，可拼接出x的完整二进制表示，即f'(y) = x。

算法步骤

1. 特殊处理：若n=1，直接返回[1]（双射唯一），无需调用Encode（满足T=0）。
2. 计算二进制位数：确定n所需的二进制位数bits（如n=1e5需17位，因2^16=65536 < 1e5 < 2^17=131072）。
3. 分组查询：对每个二进制位k，构造S_k（第k位为1的所有x），调用Encode(S_k)得到S'_k，并标记S'_k中所有y的第k位为1。
4. 构造逆映射：根据每个y的二进制标记，拼接出对应的x（即f'(y)）。

代码实现

#include "interaction.h"
#include <vector>
using namespace std;

vector<int> Decode(int n, int T) {
    vector<int> ans(n);
    // 特殊情况：n=1时，逆映射唯一为1，无需调用Encode（满足T=0）
    if (n == 1) {
        ans[0] = 1;
        return ans;
    }
    // 计算需要的二进制位数（覆盖1~n的所有数）
    int bits = 0;
    while ((1 << bits) <= n) {
        bits++;
    }
    // bits_of_y[y-1] 存储f'(y)的二进制值（逐位标记）
    vector<int> bits_of_y(n, 0);
    for (int k = 0; k < bits; ++k) {
        vector<int> S;
        // 构造第k位为1的集合S
        for (int x = 1; x <= n; ++x) {
            if (x & (1 << k)) {
                S.push_back(x);
            }
        }
        // 调用Encode获取加密后的集合S'
        vector<int> res = Encode(S);
        // 标记S'中所有y的第k位为1
        for (int y : res) {
            bits_of_y[y - 1] |= (1 << k);
        }
    }
    // 拼接逆映射：bits_of_y[y-1]即为f'(y)
    for (int y = 1; y <= n; ++y) {
        ans[y - 1] = bits_of_y[y - 1];
    }
    return ans;
}

代码解释

1. 特殊处理：n=1时直接返回[1]，避免不必要的交互，满足T=0的约束。
2. 二进制位数计算：通过循环找到覆盖1~n所需的最小二进制位数bits，确保所有数都能被唯一表示。
3. 分组查询与标记：对每个二进制位k，构造集合S并调用Encode，将加密结果res中的y对应的第k位标记为1，记录在bits_of_y中。
4. 逆映射构造：bits_of_y[y-1]存储f'(y)的二进制值，直接作为结果返回，确保每个y都能映射到唯一的原像x。

复杂度分析

• 交互次数：O(log n)，仅需bits次Encode调用（如n=1e5时为17次），完全满足所有测试点的T约束。
• 通信量：O(n log n)，所有查询的集合大小总和为n * bits（如n=1e5时为1.7e6），远小于1e7的限制，避免超时。
• 时间复杂度：O(n log n)，构造集合和标记位的过程均为线性遍历，效率极高。

该算法利用二进制的唯一性，以最优的交互次数和通信量还原逆映射，适用于所有测试点，且代码简洁易懂，无交互错误风险。