1312C. C. Adding Powers

CF1312C. Adding Powers

时限: 2 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

假设你正在执行如下算法。有一个数组 $v_1, v_2, \dots, v_n$，初始时所有元素均为 $0$。你可以对该数组多次进行如下操作——在第 $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$。

输出格式

对于每个测试用例，若你能够在某一步后使数组 $v$ 等于数组 $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$ 上。