CF1312C Adding Powers 题解

题目链接：CF1312C Adding Powers

题意：

多组数据。假设你正在执行以下算法：

初始时，有一个填满零的数组 \(v_1, v_2, \ldots, v_n\)。

该算法会多次对数组进行以下操作：

• 在第 \(i\) 步（从 \(0\) 开始），你可以：
  • 要么选择位置 \(\mathrm{pos}\) \((1 \leq \mathrm{pos} \leq n)\) 并将 \(v_{\mathrm{pos}}\) 增加 \(k^i\)。
  • 要么不选择任何位置，跳过这一步。

你可以选择算法在每一步中的行为以及何时停止。

问题是：能否在某一步后使数组 \(v\) 等于给定的数组 \(a\)（对于每个 \(j\)，有 \(v_j=a_j\) ）？

数据范围：

\(1\le T \le 10^3,~1 \le n \le 30, 1\le k \le 100, 0\le a_j \le 10^{16}\)

这个题还是蛮简单的，如果目标数组能够达成，那么所有 \(a_j\) 在 \(k\) 进制分解后一定不存在重复出现的 \(i\) 。

说到这个，顺便提醒一下， \(k\) 进制下最大数码是 \(k-1\) ，不要傻fufu的去 a[i] -= pwd[j] 哦！

时间复杂度 \(\mathcal{O}(Tn\log M)\) ，其中 \(M\) 为值域。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF ((int)(1e16 + 15))
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(233))

int n,k,cnt,vis[N],pwd[N],a[N];
void clear() {
    memset(vis, 0, sizeof(vis)); memset(pwd, 0, sizeof(pwd));
}
void solve()
{
    clear(); cin >> n >> k; pwd[cnt = 0] = 1;
    for(cnt = 1; pwd[cnt - 1] < INF; ++cnt) {
        pwd[cnt] = pwd[cnt - 1] * k;
    } --cnt;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) {
        for(int j = 0; a[i]; j++) {
            vis[j] += a[i] % k; a[i] /= k;
        }
    }
    char ok = false;
    for(int i = 0; i <= cnt; i++) if(vis[i] > 1) ok = true;
    cout << (ok ? "NO" : "YES") << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}