Dotcpp  >  编程题库  >  蓝桥杯2021年第十二届国赛真题-异或变换
题目 2613:

蓝桥杯2021年第十二届国赛真题-异或变换

时间限制: 3s 内存限制: 192MB 提交: 1968 解决: 409

题目描述

小蓝有一个 01 串 s = s1 s2 s3 · · · sn。
以后每个时刻,小蓝要对这个 01 串进行一次变换。每次变换的规则相同。
对于 01 串 s = s1 s2 s3 · · · sn,变换后的 01 串 s′ = s′1 s′2 s′3· · · s′n 为:
s′1 = s1; 
s′i = sii 1 ⊕ si。
其中 a ⊕ b 表示两个二进制的异或,当 a 和 b 相同时结果为 0,当 a 和 b不同时结果为 1。
请问,经过 t 次变换后的 01 串是什么?

输入格式

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

输出格式

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

样例输入

5 3
10110

样例输出

11010

提示

【样例说明】
初始时为 10110,变换 1 次后变为 11101,变换 2 次后变为 10011,变换 3
次后变为 11010。
【评测用例规模与约定】
对于 40% 的评测用例,1 ≤ n ≤ 100, 1 ≤ t ≤ 1000。
对于 80% 的评测用例,1 ≤ n ≤ 1000, 1 ≤ t ≤ 109
对于所有评测用例,1 ≤ n ≤ 10000, 1 ≤ t ≤ 1018
标签