题意理解

我们有一个初始全为 0 的数组 ( v_1, v_2, \dots, v_n )。
第 ( i ) 步（( i ) 从 0 开始）可以选择：

• 把 ( k^i ) 加到数组的某个元素上
• 或者跳过这一步

每个 ( k^i ) 最多只能用一次（因为第 ( i ) 步只能选一个位置加一次，或者跳过）。

问：能否通过若干步（可以不使用全部步数），使数组变成给定的目标数组 ( a_1, a_2, \dots, a_n )？

关键观察

1. 每个 ( a_j ) 是若干不同的 ( k^p ) 的和

因为每一步加的数是 ( k^0, k^1, k^2, \dots )，且每个幂次只能用一次（全局）。
所以每个 ( a_j ) 必须能写成： [ a_j = \sum_{p} c_{j,p} \cdot k^p ] 其中 ( c_{j,p} \in {0, 1} )，并且对所有 ( j ) 和固定的 ( p )，(\sum_{j} c_{j,p} \le 1)（即一个幂次只能被一个元素使用一次）。

2. 转换为 ( k ) 进制表示

如果我们把 ( a_j ) 用 ( k ) 进制表示： [ a_j = \sum_{p} d_{j,p} \cdot k^p, \quad 0 \le d_{j,p} < k ] 那么：

• ( d_{j,p} ) 就是 ( a_j ) 在 ( k ) 进制下的第 ( p ) 位数字。
• 如果 ( d_{j,p} > 1 )，意味着需要重复使用 ( k^p ) 多次，这是不允许的（因为每个幂次只能用一次）。
• 如果 ( d_{j,p} = 1 )，表示该幂次被这个元素占用一次。

因此： [ \text{条件：} \forall j,p, ; d_{j,p} \in {0,1} \quad \text{且} \quad \forall p, \sum_j d_{j,p} \le 1 ]

3. 等价条件

• 对每个 ( a_j ) 做 ( k ) 进制分解。
• 检查每一位（每个幂次）是否在所有数中出现的次数 (\le 1)。
• 如果某一位出现次数 ( > 1 ) → "NO"。
• 如果某一位数字 ( \ge 2 ) → "NO"（因为那意味着同一个幂次被同一个数用了多次）。

算法步骤

1. 读入 ( n, k ) 和数组 ( a )。
2. 初始化一个数组 cnt[p] 表示幂次 ( k^p ) 被使用的次数。
3. 对每个 ( a_i )：
   • 不断除以 ( k )：
     • 取余数 ( r = a_i % k )。
     • 如果 ( r > 1 )：直接输出 "NO"（因为不能用 ( k^p ) 多次）。
     • 如果 ( r == 1 )：检查 cnt[p] 是否已经为 1，如果是则冲突 → "NO"，否则 cnt[p]++。
     • 然后 a_i /= k，p++。
   • 如果中途出错，跳出循环。
4. 如果所有数都通过检查，输出 "YES"。

例子验证

样例 1

n=4, k=100
a = [0,0,0,0]

全部为 0 → 不需要任何幂次 → "YES"

样例 2

n=1, k=2
a = [1]

1 = ( 2^0 ) → 幂次 0 使用一次 → "YES"

样例 3

n=3, k=4
a = [1,4,1]

• 1 = ( 4^0 ) → 幂次 0 被使用（位置1）
• 4 = ( 4^1 ) → 幂次 1 被使用
• 1 = ( 4^0 ) → 幂次 0 再次被使用 → 冲突 → "NO"

样例 4

n=3, k=2
a = [0,1,3]

3 的二进制是 11 → 需要 ( 2^0 ) 和 ( 2^1 ) 同时给第 3 个元素，但 1 已经用了 ( 2^0 ) → 冲突 → "NO"

样例 5

n=3, k=9
a = [0, 59049, 810]

59049 = ( 9^5 )
810 分解：
810 ÷ 9 = 90 余 0
90 ÷ 9 = 10 余 0
10 ÷ 9 = 1 余 1 → 所以 810 = ( 1 \cdot 9^0 + 0\cdot 9^1 + 0\cdot 9^2 + 1\cdot 9^3 )
检查：

• 幂次 0 出现 1 次（810 用）
• 幂次 3 出现 1 次（810 用）
• 幂次 5 出现 1 次（59049 用）
  无冲突 → "YES"

复杂度

• 每个数最多需要 ( \log_k a_{\max} ) 次除法，( a_{\max} \le 10^{16}, k \ge 2 ) → 最多约 ( 54 ) 步。
• 总复杂度 ( O(T \cdot n \cdot \log_k a_{\max}) )，足够快。

代码实现（与标程一致）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        long long k;
        cin >> n >> k;

        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        vector<int> cnt(100, 0);
        bool ok = true;

        for (int i = 0; i < n; i++) {
            long long x = a[i];
            int power = 0;
            while (x > 0) {
                int r = x % k;
                if (r > 1) {
                    ok = false;
                    break;
                }
                if (r == 1) {
                    cnt[power]++;
                    if (cnt[power] > 1) {
                        ok = false;
                        break;
                    }
                }
                x /= k;
                power++;
            }
            if (!ok) break;
        }

        cout << (ok ? "YES" : "NO") << '\n';
    }

    return 0;
}