P4804 [CCC 2016] Circle of Life

**Translated from [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)”** > You may have heard of Conway's Game of Life. Conway's Game of Life runs on a grid matrix. However, it can produce very complex structures. In this problem, we will use a simplified version of the Game of Life. This is a zero-player game. In other words, once the initial condition is given, the game runs by itself. Divide a ring into $N$ segments, and label these $N$ segments clockwise as $1,\dots,N$. Each segment is either alive (represented by `1`) or dead (represented by `0`). The game will go through $T$ rounds of “changes”. If a cell has **exactly** one adjacent cell that is alive during this change, then the cell will be alive in the next change. Otherwise, the cell will be dead. Given the initial state of the ring, find the state after $T$ changes.

The first line contains two integers $N$ and $T(3 \le N \le 100\ 000;1 \le T \le 10^{15})$. The second line contains a string of length $N$, describing the initial states of the $N$ cells. Each character is guaranteed to be either `0` or `1`. The $i$-th character represents the initial state of cell $i$.

Output a string of length $N$, representing the final state. The format is the same as the input.

#### Sample Explanation 1 Cells $1$, $N - 1$, and $N$ are adjacent, so they remain alive after one change. #### Sample Explanation 2 After one change, the state is `00011`. After two changes, the state is `10111`. For $\frac{1}{15}$ of the testdata, $N \le 15,T \le 15$. For another $\frac{6}{15}$ of the testdata, $N \le 15$. For another $\frac{4}{15}$ of the testdata, $N \le 4000,T \le 10\ 000\ 000$. Note that for all testdata, you need to use 64-bit integers. Translated by ChatGPT 5