{"problem":{"name":"「Cfz Round 3」Circle","description":{"content":"给定一个长度为 $n$ 的 $\\tt{01}$ 串 $S$ 和一个非负整数 $l$。 我们定义，对于一个 $1\\sim n$ 的排列 $t$ 和非负整数 $k$： $$f_{t,k}(i)=\\begin{cases}i & k=0\\\\f_{t,k-1}(t_i) & k \\neq 0\\end{cases}$$ 你需要构造一个 $1\\sim n$ 的排列 $p$，满足： - 对于任意一个不大","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10034"},"statements":[{"statement_type":"Markdown","content":"给定一个长度为 $n$ 的 $\\tt{01}$ 串 $S$ 和一个非负整数 $l$。\n\n我们定义，对于一个 $1\\sim n$ 的排列 $t$ 和非负整数 $k$：\n\n$$f_{t,k}(i)=\\begin{cases}i & k=0\\\\f_{t,k-1}(t_i) & k \\neq 0\\end{cases}$$\n\n你需要构造一个 $1\\sim n$ 的排列 $p$，满足：\n\n- 对于任意一个不大于 $n$ 的正整数 $i$，都满足 $p_i \\neq i$；\n- 若 $S_i$ 为 $\\tt1$，则 $f_{p,l}(i)=i$（若 $S_i$ 为 $\\tt0$ 则没有限制）；\n\n或报告无解。\n\n其中，$1\\sim n$ 的排列指满足所有不大于 $n$ 的正整数恰好出现一次的序列。\n\n## Input\n\n**本题有多组测试数据。**\n\n第一行输入一个整数 $T$，表示测试数据组数。\n\n接下来依次输入每组测试数据。对于每组测试数据：\n\n- 第一行输入两个整数 $n,l$。\n- 第二行输入一个长度为 $n$ 的 $\\tt{01}$ 串表示 $S$。\n\n## Output\n\n对于每组数据，输出一行：\n\n- 若存在满足条件的排列 $p$，则输出用空格分隔的 $n$ 个整数，表示你构造的排列 $p$；\n- 若不存在满足条件的排列 $p$，则输出 $-1$。\n\n**所有满足要求的输出均可通过。**\n\n[samples]\n\n## Note\n\n#### 「样例解释 #1」\n\n对于第 $1$ 组数据，$f_{p,3}(1)=f_{p,2}(4)=f_{p,1}(5)=f_{p,0}(1)=1$，其余数同理，所以 $p$ 为 $\\{4,3,2,5,1\\}$ 时满足条件。\n\n对于第 $2$ 组数据，可以证明不存在满足条件的排列 $p$。\n\n对于第 $3$ 组数据，$\\{2,1,4,5,3\\}$ 等也为满足条件的排列 $p$。\n\n#### 「数据范围」\n\n设 $\\sum n$ 表示单个测试点中 $n$ 的和。\n\n对于所有数据，$1 \\le T \\le 100$，$2 \\le n \\le 5\\times 10^5$，$0 \\le l \\le 10^{18}$，$\\sum n \\le 5\\times 10^5$，保证 $S$ 中只包含 $\\tt{0}$ 和 $\\tt{1}$。\n\n**只有你通过本题的所有测试点，你才能获得本题的分数。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10034","tags":["动态规划 DP","图论","洛谷原创","Special Judge","O2优化","背包 DP","素数判断,质数,筛法","构造","洛谷月赛","链表"],"sample_group":[["4\n5 3\n10011\n4 5\n1000\n5 6\n11111\n9 6\n011111011","4 3 2 5 1\n-1\n5 4 2 3 1\n3 1 2 6 4 5 9 7 8"]],"created_at":"2026-03-03 11:09:25"}}