【打表, 找规律】异或变换

题目

异或变换 - 蓝桥云课

---

题目描述

小蓝有一个 $01$ 串 $s = s_1 s_2 s_3 \cdots s_n$ 。

以后每个时刻，小蓝要对这个 $01$ 串进行一次变换。每次变换的规则相同。 对于 $01$ 串 $s = s_1 s_2 s_3 \cdots s_n$ ，变换后的 $01$ 串 $s′ = s′_1s′_2s′_3\cdots s′_n$ 为：

$s′_1 = s_1$ ;

$s′*i = s*{i−1} \oplus s_i$。

其中 $a \oplus b$ 表示两个二进制的异或，当 $a$ 和 $b$ 相同时结果为 $0$ ，当 $a$ 和 $b$ 不同时结果为 $1$ 。

请问，经过 $t$ 次变换后的 $01$ 串是什么？

输入描述

输入的第一行包含两个整数 $n, t$ ，分别表示 $01$ 串的长度和变换的次数。

第二行包含一个长度为 $n$ 的 $01$ 串。

输出描述

输出一行包含一个 $01$ 串，为变换后的串。

输入输出样例

示例

输入

5 3
10110
copy

输出

11010
copy

样例说明

初始时为 $10110$ ，变换 $1$ 次后变为 $11101$ ，变换 $2$ 次后变为 $10011$ ，变换 $3$ 次后变为 $11010$ 。

评测用例规模与约定

对于 $40$ % 的评测用例， $1 ≤ n ≤ 100, 1 ≤ t ≤ 1000$ 。

对于 $80$ % 的评测用例， $1 ≤ n ≤ 1000, 1 ≤ t ≤ 10^9$ 。

对于所有评测用例， $1 ≤ n ≤ 10000, 1 ≤ t ≤ 10^{18}$ 。

运行限制

• 最大运行时间：3s
• 最大运行内存: 256M

解题

方法一：暴力 模拟

思路

没有思路的话可以直接暴力模拟拿40%的分。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] tmp = in.readLine().split(" ");
        int n = Integer.parseInt(tmp[0]);
        int t = Integer.parseInt(tmp[1]);
        char[] s = in.readLine().toCharArray();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = s[i] - '0';
        while (t-- > 0) {
            for (int i = n - 1; i >= 1; --i) a[i] ^= a[i - 1];
        }
        for (int x : a) System.out.print(x);
    }
}

方法二：打表找规律

思路

$t$ 最大的数据范围是 $[1, 10^{18}]$ ，显然不能靠模拟过全部测试用例。

遇到这种多次变换的题难免想到变换存在一个周期 $p$ 使得串 $s$ 变换 $p$ 次后与 $s$ 相同，那么变换 $2p, 3p, \dots$ 次后也应该与 $s$ 相同，此时我们只需要模拟 $t \mod p$ 次变换就可以得到变换后的串。

最简单的方法是打表找找周期有什么规律，通过打表发现周期 $p$ 与 $s$ 的长度 $n$ 有关：

import java.util.*;
import java.io.*;

public class Test {
    public static void main(String[] args) throws IOException {
        for (int i = 1; i <= 20; ++i) {
            int n = i;
            char[] s = Integer.toString(1 << (i - 1), 2).toCharArray();
            int[] a = new int[n];
            for (int j = 0; j < n; ++j) a[j] = s[j] - '0';
            int[] ori = a.clone();
            int cnt = 0;
            outer: while (true) {
                for (int j = n - 1; j > 0; --j) a[j] ^= a[j - 1];
                ++cnt;
                for (int j = 0; j < n; ++j) {
                    if (a[j] != ori[j]) continue outer;
                }
                break;
            }
            System.out.println("length: " + n + ", peroid: " + cnt);
        }
    }
}

n = 1, p = 1
n = 2, p = 2
n = 3, p = 4
n = 4, p = 4
n = 5, p = 8
n = 6, p = 8
n = 7, p = 8
n = 8, p = 8
n = 9, p = 16
n = 10, p = 16
n = 11, p = 16
n = 12, p = 16
n = 13, p = 16
n = 14, p = 16
n = 15, p = 16
n = 16, p = 16
n = 17, p = 32
n = 18, p = 32
n = 19, p = 32
n = 20, p = 32

显然， $p = 2^{(\lfloor \log_2{n} \rfloor + 1)}$ ，用人话说就是：周期等于第一个大于等于 $n$ 的 $2$ 的幂。

有了周期接下来的就是模拟了，要注意：$t$ 的数据范围会爆int，要输入long。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long t = in.nextLong();
        in.nextLine();
        char[] s = in.nextLine().toCharArray();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = s[i] - '0';
        int p = 1;
        while (p < n) p <<= 1;
        t %= p;
        while (t-- > 0) {
            for (int i = n - 1; i > 0; --i) a[i] ^= a[i - 1];
        }
        for (int x : a) System.out.print(x);
    }
}