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