luogu#P10034. 「Cfz Round 3」Circle

    ID: 13995 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>动态规划,dp图论洛谷原创Special JudgeO2优化背包素数判断,质数,筛法构造洛谷月赛链表

「Cfz Round 3」Circle

题目描述

给定一个长度为 nn01\tt{01}SS 和一个非负整数 ll

我们定义,对于一个 1n1\sim n 的排列 tt 和非负整数 kk

$$f_{t,k}(i)=\begin{cases}i & k=0\\f_{t,k-1}(t_i) & k \neq 0\end{cases} $$

你需要构造一个 1n1\sim n 的排列 pp,满足:

  • 对于任意一个不大于 nn 的正整数 ii,都满足 piip_i \neq i
  • SiS_i1\tt1,则 fp,l(i)=if_{p,l}(i)=i(若 SiS_i0\tt0 则没有限制);

或报告无解。

其中,1n1\sim n 的排列指满足所有不大于 nn 的正整数恰好出现一次的序列。

输入格式

本题有多组测试数据。

第一行输入一个整数 TT,表示测试数据组数。

接下来依次输入每组测试数据。对于每组测试数据:

  • 第一行输入两个整数 n,ln,l
  • 第二行输入一个长度为 nn01\tt{01} 串表示 SS

输出格式

对于每组数据,输出一行:

  • 若存在满足条件的排列 pp,则输出用空格分隔的 nn 个整数,表示你构造的排列 pp
  • 若不存在满足条件的排列 pp,则输出 1-1

所有满足要求的输出均可通过。

4
5 3
10011
4 5
1000
5 6
11111
9 6
011111011
4 3 2 5 1
-1
5 4 2 3 1
3 1 2 6 4 5 9 7 8

提示

「样例解释 #1」

对于第 11 组数据,fp,3(1)=fp,2(4)=fp,1(5)=fp,0(1)=1f_{p,3}(1)=f_{p,2}(4)=f_{p,1}(5)=f_{p,0}(1)=1,其余数同理,所以 pp{4,3,2,5,1}\{4,3,2,5,1\} 时满足条件。

对于第 22 组数据,可以证明不存在满足条件的排列 pp

对于第 33 组数据,{2,1,4,5,3}\{2,1,4,5,3\} 等也为满足条件的排列 pp

「数据范围」

n\sum n 表示单个测试点中 nn 的和。

对于所有数据,1T1001 \le T \le 1002n5×1052 \le n \le 5\times 10^50l10180 \le l \le 10^{18}n5×105\sum n \le 5\times 10^5,保证 SS 中只包含 0\tt{0}1\tt{1}

只有你通过本题的所有测试点,你才能获得本题的分数。