luogu#P10034. 「Cfz Round 3」Circle
「Cfz Round 3」Circle
题目描述
给定一个长度为 的 串 和一个非负整数 。
我们定义,对于一个 的排列 和非负整数 :
$$f_{t,k}(i)=\begin{cases}i & k=0\\f_{t,k-1}(t_i) & k \neq 0\end{cases} $$你需要构造一个 的排列 ,满足:
- 对于任意一个不大于 的正整数 ,都满足 ;
- 若 为 ,则 (若 为 则没有限制);
或报告无解。
其中, 的排列指满足所有不大于 的正整数恰好出现一次的序列。
输入格式
本题有多组测试数据。
第一行输入一个整数 ,表示测试数据组数。
接下来依次输入每组测试数据。对于每组测试数据:
- 第一行输入两个整数 。
- 第二行输入一个长度为 的 串表示 。
输出格式
对于每组数据,输出一行:
- 若存在满足条件的排列 ,则输出用空格分隔的 个整数,表示你构造的排列 ;
- 若不存在满足条件的排列 ,则输出 。
所有满足要求的输出均可通过。
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」
对于第 组数据,,其余数同理,所以 为 时满足条件。
对于第 组数据,可以证明不存在满足条件的排列 。
对于第 组数据, 等也为满足条件的排列 。
「数据范围」
设 表示单个测试点中 的和。
对于所有数据,,,,,保证 中只包含 和 。
只有你通过本题的所有测试点,你才能获得本题的分数。