{"problem":{"name":"[CCPC 2023 北京市赛] 替换","description":{"content":"给定一个长度为 $n$、字符集为 `01?` 的字符串 $s_1s_2 \\cdots s_n$。 对于任意 $k \\in [1,n]$，考察字符串 $T_k = t_1 t_2 \\cdots t_n$，其中对于 $1 \\le i \\le n$， - 若 $s_i \\ne$ `?`，则 $t_i = s_i$； - 否则，若 $i \\le k$，$t_i =$ `0`； - 否则 $t_i = ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10040"},"statements":[{"statement_type":"Markdown","content":"给定一个长度为 $n$、字符集为 `01?` 的字符串 $s_1s_2 \\cdots s_n$。\n\n对于任意 $k \\in [1,n]$，考察字符串 $T_k = t_1 t_2 \\cdots t_n$，其中对于 $1 \\le i \\le n$，\n\n- 若 $s_i \\ne$ `?`，则 $t_i = s_i$；\n- 否则，若 $i \\le k$，$t_i =$ `0`；\n- 否则 $t_i = t_{i-k}$，你可以通过递归地算出 $t_{i-k}$ 得到 $t_i$。\n\n容易发现 $T_k$ 的字符集为 `01`。你需要对所有 $k \\in [1,n]$ 求出 $T_k$ 中 `1` 的个数。\n\n## Input\n\n输入的第一行一个整数 $n (1 \\le n \\le 10^5)$ 表示字符串长度，第二行一个长度为 $n$、字符集为 `01?` 的字符串 $s_1s_2\\cdots s_n$。\n\n## Output\n\n输出 $n$ 行，第 $i$ 行一个整数表示 $T_i$ 中 `1` 的个数。\n\n[samples]\n\n## Note\n\n$T_1 =$ `10011`，$T_2 =$ `10111`，$T_3 =$ `10010`，$T_4 =$ `10011`，$T_5 =$ `10010`。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10040","tags":["2023","省赛/邀请赛"],"sample_group":[["5\n10?1?","3\n4\n2\n3\n2"]],"created_at":"2026-03-03 11:09:25"}}