数字变换 (transform)

时间限制： 1.5 秒

空间限制： 512 MiB

相关文件： 题目目录

题目描述

小 C 设计了一种变换 $F$ ，若输入 $\left[0,2^9\right)$ 中的整数，则输出也是 $\left[0,2^9\right)$ 中的整数。

记 $\oplus$ 为按位异或运算，即 C++/Java/Python 中的 ^ 运算符。

若 $x,k$ 均为 $\left[0,2^3\right)$ 内的整数，定义 $f(x,k)=\left(\left(x^2+k^2\right)\bmod 2^3\right)\oplus k$ 。

若 $x$ 为 $\left[0,2^9\right)$ 内的整数， $k$ 为 $\left[0,2^3\right)$ 内的整数。将 $x$ 的二进制表示进行高位补零的操作，使其恰好为 $9$ 位。 $g(x,k)$ 将会把这 $9$ 个二进制位分为高三位、中三位、低三位三组并将其视为三个数字分别进行变换，具体如下图所示：

d8ba5ce4-c1cd-4a95-9d29-13deb7ce623d.png

记 $f_0$ 为 $F$ 变换的输入值，并定义 $f_i=g(f_{i-1},k_i)$ ， $i\in\{1,2,3,\cdots,m\}$ ，则 $f_m$ 为 $F$ 变换的输出值。长为 $m$ 的序列 $k$ 是一个给定的参数序列，并且其中每个数字都是 $\left[0,2^3\right)$ 之间的整数。

现在小 C 有 $n$ 个经过 $F$ 变换后得到的值，分别为 $a_1,a_2,\cdots,a_n$ ，小 C 想知道它们对应的输入分别是什么。

输入格式

从标准输入读入数据。

第一行两个正整数 $n,m$ 。

第二行有 $m$ 个非负整数，分别为 $k_1,k_2,\cdots,k_m$ 。

第三行有 $n$ 个非负整数，分别为 $a_1,a_2,\cdots,a_n$ 。

输出格式

输出到标准输出。

输出一行 $n$ 个非负整数，表示 $a_1,a_2,\cdots,a_n$ 对应的输入。

样例1输入

1 2
3 5
504

样例1输出

样例1解释

可以枚举可能的输入并验证。

若枚举到的输入为 $f_0=101$ 。

对于 $f_1=g(101,3)$ 来说： $a=1$ ， $b=4$ ， $c=5$ ， $c\oplus f(b,3)=7$ ， $a\oplus f(c,3)=0$ ，故 $f_1=312$ 。

对于 $f_2=g(312,5)$ 来说： $a=4$ ， $b=7$ ， $c=0$ ， $c\oplus f(b,5)=7$ ， $a\oplus f(c,5)=0$ ，故 $f_2=504$ 。

因此若输入为 $101$ ，则输出为 $504$ ，因此 $101$ 是其对应的输入。

如果枚举的输入是别的数字，可以同上验证其输出不是 $504$ 。

样例2

见题目目录下的 2.in 与 2.ans。

样例3

见题目目录下的 3.in 与 3.ans。

子任务

$80\\%$ 的测试数据满足： $1\le n\le 100$ ， $1\le m\le 20$ 。

$100\\%$ 的测试数据满足： $1\le n\le 5 \times 10^{5}$ ， $1\le m \le10^{3}$ ， $0\le k_i<2^3$ ， $0\le a_i<2^9$ ，且只有唯一的输入能够得到这些输出。

Solution

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    private static int f(int x, int k) {
        return (((x * x + k * k) & 7) ^ k);
    }

    private static int transform(int value, int k) {
        int a = (value >>> 6) & 7;
        int b = (value >>> 3) & 7;
        int c = value & 7;

        int nextA = b;
        int nextB = c ^ f(b, k);
        int nextC = a ^ f(c, k);
        return (nextA << 6) | (nextB << 3) | nextC;
    }

    public static void main(String[] args) throws Exception {
        FastScanner scanner = new FastScanner();
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int[] keys = new int[m];
        for (int i = 0; i < m; i++) {
            keys[i] = scanner.nextInt();
        }

        int[] inverse = new int[512];
        for (int start = 0; start < 512; start++) {
            int value = start;
            for (int key : keys) {
                value = transform(value, key);
            }
            inverse[value] = start;
        }

        StringBuilder answer = new StringBuilder(n * 4);
        for (int i = 0; i < n; i++) {
            int output = scanner.nextInt();
            if (i > 0) {
                answer.append(' ');
            }
            answer.append(inverse[output]);
        }
        System.out.println(answer);
    }

    private static final class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int pointer;
        private int length;

        private int read() throws IOException {
            if (pointer >= length) {
                length = input.read(buffer);
                pointer = 0;
                if (length <= 0) {
                    return -1;
                }
            }
            return buffer[pointer++];
        }

        int nextInt() throws IOException {
            int character;
            do {
                character = read();
            } while (character <= ' ' && character != -1);

            int value = 0;
            while (character > ' ') {
                value = value * 10 + character - '0';
                character = read();
            }
            return value;
        }
    }
}

ccf40-2数字变换 (transform)