数字变换

GitHub跳转原题关系图Canvas 关系图返回列表

由于状态只有 512 个，预计算所有输入经过参数序列后的输出，再建立输出到输入的逆映射。

OJ: shumeng

题目 ID: CSP202512B

难度:未知

标签:位运算模拟状态压缩预处理

日期: 2026-07-31 16:22

目录

  1. 形式化题目
  2. 思路
    1. 枚举全部初始值
    2. 按位拆合
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

9 位整数 xx（0≤x<290 \le x < 2^9）经过 mm 步变换得到输出。每步使用参数 kik_i，先把 xx 的 9 位二进制分成高、中、低三组 3 位数字 (a,b,c)(a,b,c)，再按规则

(a′,b′,c′)=(b, c⊕f(b,ki), a⊕f(c,ki)),f(x,k)=((x2+k2) mod 23)⊕k (a',b',c')=(b,\ c \oplus f(b,k_i),\ a \oplus f(c,k_i)),\qquad f(x,k)=((x^2+k^2)\bmod 2^3)\oplus k

组合回 9 位。给定 nn 个输出值，求它们各自唯一的输入。

思路

状态空间极小，直接正向建逆映射。

枚举全部初始值

9 位整数只有 29=5122^9 = 512 种。对每个初始值完整模拟 mm 步变换，得到输出，并记录 inverse[输出] = 初始值。

按位拆合

每次变换先把 value 拆成三组 3 位数字，套用变换公式后再拼回 9 位。题目保证每个输出对应唯一输入，所以直接查表即可。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:22
 * update_at: 2026-08-17 23:05
 */
#include <bits/stdc++.h>
using namespace std;

// 单次 3 位变换 f(x,k)，x 与 k 均小于 2^3
int f_value(int x, int k) {
    return (((x * x + k * k) & 7) ^ k);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> k(m); // 参数序列
    for (int i = 0; i < m; i++) cin >> k[i];

    // 9 位状态只有 512 种：枚举所有初始值，正向模拟得到输出并建立逆映射
    vector<int> inverse(512, -1);
    for (int start = 0; start < 512; start++) {
        int value = start;
        for (int step_index = 0; step_index < m; step_index++) {
            int step = k[step_index];
            // 把 9 位拆成高、中、低三组 3 位数字 a,b,c
            int a = (value >> 6) & 7;
            int b = (value >> 3) & 7;
            int c = value & 7;
            // 题目给定的 g 变换：
            // 新 a = b，新 b = c ^ f(b,k)，新 c = a ^ f(c,k)
            int na = b;
            int nb = c ^ f_value(b, step);
            int nc = a ^ f_value(c, step);
            value = (na << 6) | (nb << 3) | nc;
        }
        inverse[value] = start; // 题目保证每个输出只对应唯一输入
    }

    // 每个查询直接查表恢复输入
    for (int i = 0; i < n; i++) {
        int value;
        cin >> value;
        if (i) cout << ' ';
        cout << inverse[value];
    }
    cout << '\n';
    return 0;
}

复杂度

预处理 O(512⋅m)O(512 \cdot m)，查询 O(n)O(n)，空间复杂度 O(m+512)O(m + 512)。

总结

当状态空间足够小时，正向枚举全部状态并建立逆映射，比推导逐步逆变换简单可靠。本题还体现了位运算拆位拼位的基本操作：右移、与 7、左移、或。