CF1213 C. Adding Powers（进制）

题目传送

题意：给定一个数组v和k，要使一个空数组a变成v，第i步可以任意在a中选一个数加上$k^i$ki或跳过这一步。

分析：将数组v中的数字转换为k进制表示，若每一位都为1或0，说明可以由k的次方相加得到，k的每一次方只能用一次，用vis记录。

Code：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <sstream>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & -x)
#define lrt nl, nr, rt << 1
#define rrt nl, nr, rt << 1 | 1
const ll Inf = 1e18;
const int inf = 0x3f3f3f3f;
inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
	return f * x;
}

int pos;
ll an[50];
int bit[100];
int vis[100];

//10进制转k进制
void tentok(ll x, int k)
{
	pos = 1;
	while (x) {
		bit[pos++] = x % k;
		x /= k;
	}
}

int main(void)
{
	int t;
	cin >> t;
	while (t--) {
		memset(vis, 0, sizeof(vis));
		int n, k;
		cin >> n >> k;
		for (int i = 1; i <= n; i++) cin >> an[i];
		int flag = 1;
		for (int i = 1; i <= n; i++) {
			tentok(an[i], k);
			for (int j = 1; j < pos; j++) {
				//若该位大于1或k的该次方被用过
				if (bit[j] > 1 || (bit[j] == 1 && vis[j])) {
					flag = 0;
					break;
				}
				if(bit[j] == 1) vis[j] = 1; //标记被用过
			}
			if (!flag) break;
		}
		if (flag) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}