← 返回题目列表

AtCoder · pakencamp_2019_day4_g

G. 三个条件

中文机器翻译题面 查看原题

配点: 100 点

問題文

我喜欢寿司。

顺便说一下,整数 X 是 您也可以写 n 数字 a 这是一个基数。最上面的数字 也有可能是 0 。
另外, 如果我们只为第F(X) 是 您也可以写 X 可以得到第 a 基本表示法中的数字总和 10 它表示为基数。例如, 在a = 7, X = 562 的情况下,F(X) = 13 。 求放置超过

现在,下一个 3 使得两个条件同时满足。 可以视为 X 的升序排列的整数 请输出 K 件。

  • F(X) = m.
  • X' \ mod \ p = t. (但是,X' 是 您也可以写 X 该值应乘以 10 整数转换为基数) 所有整数使得
  • s_i = 0 对于 i (1 \leq i \leq n) ,一个整数 上面写着 X 可以得到第 a^{n-i} 地点是 0 。
    • 例如, 当分解为n = 7,a = 10,s = 1110110 的情况下,X 可以得到第 1000 和 必须是 1 地点是 0 。

但是,如果这样的整数 如果少于 K ,则按降序输出所有满足条件的整数后, 请输出 -1 。

有关输出格式的详细信息,请参阅“输出”部分。

制約

  • 1 \leq n \leq 100.
  • 2 \leq a \leq 1 \ 000 \ 000.
  • 0 \leq m \leq 600.
  • 2 \leq p \leq 600.
  • 0 \leq t < p.
  • 1 \leq K \leq 2 \ 000.
  • s_i 是 您也可以写 0 或 至少 1.
  • n, a, m, p, t, K 是 您也可以写 10 是以基数表示的整数。

部分点

该问题分为多个子任务,如果您正确回答了该子任务中的所有测试用例,则视为您正确回答了该子任务。
提交的源代码的分数是您正确回答的子作业分数的总和。

  1. (7 点) m = 1.
  2. (8 点) n \leq 6,a \leq 10.
  3. (24 点) n \leq 32,a = 2.
  4. (29 点) n \leq 50,a \leq 10,m \leq 50,p \leq 50.
  5. (23 点) a \geq m.
  6. (9 分) 没有其他限制。

入力

输入是按以下格式从标准输入给出的。

n a m p t K
s_1s_2s_3s_4...s_n

出力

满足条件的整数为 如果超过 K ,请按以下格式输出。

(小さい方から 1 番目の整数の情報)
(小さい方から 2 番目の整数の情報)
(小さい方から 3 番目の整数の情報)
:
(小さい方から K 番目の整数の情報)

另外,如果满足条件的整数是 如果数量小于 K ,请按以下格式输出。 (这里,满足条件的整数个数为 K' 。 )

(小さい方から 1 番目の整数の情報)
(小さい方から 2 番目の整数の情報)
(小さい方から 3 番目の整数の情報)
:
(小さい方から K' 番目の整数の情報)
-1

然而,对于整数信息,要输出的整数是 当表示为 g_{n-1}a^{n-1}+g_{n-2}a^{n-2}+...+g_0a^0 (0 \leq g_i \leq a-1) 时,请按照以下格式在一行中输出。

g_{n-1} g_{n-2} g_{n-3} ... g_{0}

入力例 1

3 10 1 5 0 2
111

出力例 1

0 1 0
1 0 0

满足条件的整数为 只有10, 100 。 它是一个
10 是 您也可以写 2 位的整数,但最高位是 可能是 0 ,所以010 满足条件。 请注意,此输入示例是一个小作业。 1 约束。


入力例 2

6 10 26 241 74 25
111110

出力例 2

0 6 6 5 9 0
0 8 8 2 8 0
1 0 9 9 7 0
1 9 6 7 3 0
2 8 3 4 9 0
3 2 6 8 7 0
3 4 8 5 6 0
3 9 1 9 4 0
4 7 8 7 0 0
5 4 3 7 7 0
5 6 5 4 6 0
5 8 7 1 5 0
6 0 8 8 4 0
6 7 3 9 1 0
6 9 5 6 0 0
7 1 7 2 9 0
7 6 0 6 7 0
7 8 2 3 6 0
8 2 5 7 4 0
8 4 7 4 3 0
8 6 9 1 2 0
8 9 0 8 1 0
9 3 4 1 9 0
-1

在此输入示例中,满足条件的整数为 只有 23 块。 由于少于
K=25 ,所以最后一行包含 如果输出 -1 ,就会得到正确答案。


入力例 3

3 2 3 7 0 2000
111

出力例 3

1 1 1
-1

入力例 4

40 23 166 240 130 1117
1000000000100000000010000000001000000000

出力例 4

-1

满足条件的整数为 如果超过 0 在某些情况下,这是事实。