P10040 [CCPC 2023 Beijing Municipal Contest] Replacement

Given a string $s_1 s_2 \cdots s_n$ of length $n$ over the alphabet `01?`. For any $k \in [1,n]$, consider the string $T_k = t_1 t_2 \cdots t_n$, where for $1 \le i \le n$: - If $s_i \ne$ `?`, then $t_i = s_i$. - Otherwise, if $i \le k$, then $t_i =$ `0`. - Otherwise, $t_i = t_{i-k}$. You can compute $t_i$ by recursively finding $t_{i-k}$. It is easy to see that the alphabet of $T_k$ is `01`. You need to compute, for all $k \in [1,n]$, the number of `1` in $T_k$.

The first line contains an integer $n \ (1 \le n \le 10^5)$, representing the length of the string. The second line contains a string $s_1 s_2 \cdots s_n$ of length $n$ over the alphabet `01?`.

Output $n$ lines. On the $i$-th line, output one integer representing the number of `1` in $T_i$.

$T_1 =$ `10011`, $T_2 =$ `10111`, $T_3 =$ `10010`, $T_4 =$ `10011`, $T_5 =$ `10010`. Translated by ChatGPT 5