2613 问题 A: 蓝桥杯2021年第十二届国赛真题-异或变换
时间限制: 1s
内存限制: 128MB 提交: 2196 解决: 464
题目描述
小蓝有一个 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 串。
提示
【样例说明】
初始时为 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。