← 返回题目列表

Codeforces · 1312/C

C. 添加权力

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

假设您正在执行以下算法。有一个数组 $$$v_1, v_2, \dots, v_n$$$ 在开始处填充零。以下操作多次应用于数组 - 在第 $$$i$$$ 步骤($$$0$$$ 索引),您可以:

- 选择位置 $$$pos$$$ ($$$1 \le pos \le n$$$) 并将 $$$v_{pos}$$$ 增加 $$$k^i$$$;
- 或不选择任何位置并跳过此步骤。

您可以选择算法在每个步骤中的行为方式以及何时停止。问题是:经过某个步骤后,您能否使数组 $$$v$$$ 等于给定数组 $$$a$$$ (对于每个 $$$j$$$,$$$v_j = a_j$$$)?

输入

第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 1000$$$) — 测试用例的数量。接下来的 $$$2T$$$ 行包含测试用例 - 每个测试用例两行。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 30$$$, $$$2 \le k \le 100$$$) — 算法中使用的数组 $$$v$$$ 和 $$$a$$$ 的大小以及值 $$$k$$$。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{16}$$$) — 您想要实现的数组。

输出

对于每个测试用例,如果在某个步骤后可以实现数组 $$$a$$$,则打印 YES(不区分大小写),否则打印 NO(不区分大小写)。

示例

输入 #1

5
4 100
0 0 0 0
1 2
1
3 4
1 4 1
3 2
0 1 3
3 9
0 59049 810

输出 #1

YES
YES
NO
NO
YES

注意

在第一个测试用例中,您可以在第$$$0$$$步骤之前停止算法,或者多次不选择任何位置并停止算法。

在第二个测试用例中,您可以将 $$$k^0$$$ 添加到 $$$v_1$$$ 并停止算法。

在第三个测试用例中,您无法在数组 $$$v$$$ 中创建两个 $$$1$$$。

在第五个测试用例中,您可以跳过$$$9^0$$$和$$$9^1$$$,然后将$$$9^2$$$和$$$9^3$$$添加到$$$v_3$$$,跳过$$$9^4$$$,最后将$$$9^5$$$添加到$$$v_2$$$。