[蓝桥杯 2021 国 ABC] 异或变换

Luogu

IDLGP8763

Time1000ms

Memory128MB

DifficultyP4

2021分治位运算蓝桥杯国赛

小蓝有一个 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^{\prime}=s_{1}^{\prime} s_{2}^{\prime} s_{3}^{\prime} \cdots s_{n}^{\prime}$ 为： $$ \begin{aligned} &s_{1}^{\prime}=s_{1} \\ &s_{i}^{\prime}=s_{i-1} \oplus s_{i} \end{aligned} $$ 其中 $a \oplus b$ 表示两个二进制的异或, 当 $a$ 和 $b$ 相同时结果为 $0$ , 当 $a$ 和 $b$ 不同时结果为 $1$ 。请问, 经过 $t$ 次变换后的 01 串是什么? ## Input 输入的第一行包含两个整数 $n, t$, 分别表示 01 串的长度和变换的次数。第二行包含一个长度为 $n$ 的 01 串。 ## Output 输出一行包含一个 01 串, 为变换后的串。 [samples] ## Note **【样例说明】** 初始时为 `10110` , 变换 1 次后变为 `11101` , 变换 2 次后变为 `10011` , 变换 3 次后变为 `11010`。 **【评测用例规模与约定】** 对于 $40 \%$ 的评测用例, $1 \leq n \leq 100,1 \leq t \leq 1000$。对于 $80 \%$ 的评测用例, $1 \leq n \leq 1000,1 \leq t \leq 10^{9}$。对于所有评测用例, $1 \leq n \leq 10000,1 \leq t \leq 10^{18}$。蓝桥杯 2021 国赛 A 组 F 题（B 组 G 题，C 组 G 题）。

Samples

Input #1

5 3
10110

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2021 国 ABC] 异或变换",
    "description": {
      "content": "小蓝有一个 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^{\\prime}=s_{1}^{\\prime} s_{2}^{\\prime} s_{3}^{\\prime} \\cdo",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8763"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小蓝有一个 01 串 $s=s_{1} s_{2} s_{3} \\cdots s_{n}$。\n\n以后每个时刻, 小蓝要对这个 01 串进行一次变换。每次变换的规则相同。 对于 01 串 $s=s_{1} s_{2} s_{3} \\cdots s_{n}$, 变换后的 01 串 $s^{\\prime}=s_{1}^{\\prime} s_{2}^{\\prime} s_{3}^{\\prime} \\cdo...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments