[CCC2016] 生命中的圆
题目描述
**译自 [CCC2016](https://cemc.math.uwaterloo.ca/contests/computing/2016/index.html) Senior T5「[Circle of Life](https://cemc.math.uwaterloo.ca/contests/computing/2016/stage%201/seniorEn.pdf)」**
> 也许你听说过康威生命游戏(Conway's Game of Life)。康威生命游戏适用于方格组成的矩阵。但它可以产生十分复杂的结构。在这道题目中,我们将使用简化版的生命游戏来虐你。
这个游戏是 0 人游戏,换句话说,只要给定初始条件,这个游戏就能自己进行下去。
将一个圆环分为 $N$ 段,将这 $N$ 段顺时针依次编为 $1,\dots,N$ 号。每一段要么是活的(以 `1` 表示),要么是死的(以 `0` 表示)。
游戏会进行 $T$ 轮「变化」。如果一个方格**恰好**有一个相邻的方格在这次变化中存活,那么该方格会在下次变化中存活。否则,该方格会死亡。
给定圆环的初始状态,求经过 $T$ 次变化之后的状态。
输入输出格式
输入格式
第一行,两个整数 $N$ 和 $T(3 \le N \le 100\ 000;1 \le T \le 10^{15})$。
第二行,一个长度为 $N$ 的字符串,表示 $N$ 个方格的初始状态。保证每个字符只有 `0` 或 `1` 两种可能。第 $i$ 位表示编号为 $i$ 的方格的初始状态。
输出格式
输出一个长度为 $N$ 的字符串,表示最终的状态。格式同输入。
输入输出样例
输入样例 #1
7 1
0000001
输出样例 #1
1000010
输入样例 #2
5 3
01011
输出样例 #2
10100
说明
#### 样例解释 1
方格 $1$ 和 $N - 1$ 和 $N$ 相邻,因此在一次变化后仍存活。
#### 样例解释 2
一次变化后,状态为 ` 00011`。
两次变化后,状态为 ` 10111`。
对于 $\frac{1}{15}$ 的数据,$N \le 15,T \le 15$。
对于另外的 $\frac{6}{15}$ 的数据,$N \le 15$。
对于另外的 $\frac{4}{15}$ 的数据,$N \le 4000,T \le 10\ 000\ 000$。
注意对于所有的数据,你需要使用 64 位整数。