#include <vector>
#include <cstdint>
#include <random>
using namespace std;
// 使用 Mersenne 素数作为哈希模数
const uint64_t P = 2147483647ULL;
// 生成稳定的随机权重数组，Aisha 和 Basma 共用这个伪随机序列
vector<uint64_t> get_W() {
vector<uint64_t> W(1056);
mt19937 rng(114514); // 固定种子
for (int i = 0; i < 1056; i++) {
W[i] = (rng() % (P - 1)) + 1;
}
return W;
}
extern vector<bool> send_packet(vector<bool> A);
void send_message(vector<bool> M, vector<bool> C) {
// 找出 16 个安全通道
vector<int> safe_cols;
for (int i = 0; i < 31; i++) {
if (!C[i]) safe_cols.push_back(i);
}
int S = M.size();
vector<bool> D(1056, 0);
// 填充消息和结束符（1作为分隔符）
for (int i = 0; i < S; i++) {
D[31 + i] = M[i];
}
D[31 + S] = 1; // 结束符，之后默认全为 0
vector<uint64_t> W = get_W();
uint64_t hash = 0;
// 计算 31 位哈希
for (int k = 31; k < 1056; k++) {
if (D[k]) {
hash = (hash + W[k]) % P;
}
}
// 将 31 位哈希存入前 31 个比特中
for (int k = 0; k < 31; k++) {
D[k] = (hash >> k) & 1;
}
// 将 1056 个比特分配到 66 个数据包的安全通道中
for (int i = 0; i < 66; i++) {
vector<bool> A(31, 0); // 不安全的通道填 0 即可
for (int j = 0; j < 16; j++) {
A[safe_cols[j]] = D[i * 16 + j];
}
send_packet(A);
}
}
// 封装一个结构体来加速 DFS，避免传参和 Lambda 捕获开销
struct DFS_Solver {
uint32_t exp_contrib[31][16];
uint64_t act_contrib[31][16];
vector<int> best_cols;
bool found;
int path[16];
void run(int c, int j, uint32_t cur_exp, uint64_t cur_act) {
if (found) return; // 找到就立刻退出
if (j == 16) {
// 校验哈希是否匹配
if (cur_exp == cur_act % P) {
best_cols.assign(path, path + 16);
found = true;
}
return;
}
// 剪枝：剩余可选的通道数不够填满 16 个
if (31 - c < 16 - j) return;
// 选择当前列 c
path[j] = c;
run(c + 1, j + 1, cur_exp | exp_contrib[c][j], cur_act + act_contrib[c][j]);
// 不选择当前列 c
run(c + 1, j, cur_exp, cur_act);
}
};
vector<bool> receive_message(vector<vector<bool>> R) {
vector<uint64_t> W = get_W();
DFS_Solver solver;
solver.found = false;
// 初始化预计算数组
for(int c=0; c<31; c++) {
for(int j=0; j<16; j++) {
solver.exp_contrib[c][j] = 0;
solver.act_contrib[c][j] = 0;
}
}
// 预计算：如果第 c 列被选作第 j 个安全通道，它对哈希的贡献是多少
for (int c = 0; c < 31; c++) {
for (int j = 0; j < 16; j++) {
for (int i = 0; i < 66; i++) {
int k = i * 16 + j;
if (R[i][c]) {
if (k < 31) {
solver.exp_contrib[c][j] |= (1U << k);
} else {
solver.act_contrib[c][j] += W[k];
}
}
}
}
}
// 开启 3 亿次枚举搜索
solver.run(0, 0, 0, 0);
// 根据找到的最优安全通道提取数据
vector<bool> D(1056, 0);
for (int i = 0; i < 66; i++) {
for (int j = 0; j < 16; j++) {
D[i * 16 + j] = R[i][solver.best_cols[j]];
}
}
// 从后往前寻找结束符 `1`
int sep = 1055;
while (sep >= 31 && !D[sep]) {
sep--;
}
// 解析出实际长度 S 和原始消息 M
int S = sep - 31;
vector<bool> res(S);
for (int i = 0; i < S; i++) {
res[i] = D[31 + i];
}
return res;
}
