使用一组特定的规则将数组中的元素归零

Question

给定n个数字，您可以多次执行以下操作：选择数字的任何子集，其中没有一个是0。将子集中的数字减少1，将不在子集中的数量增加K。

是否可以执行操作，使除其中一个数字外的所有数字变为0？

输入：第一行包含测试用例T的数量。后面是2*T行，每个用例2行。测试用例的第一行包含数字n和K。下一行包含n个数字，a_1…a_n.

输出：输出T线，每个测试用例对应一条。对于测试用例，如果存在所描述的操作序列，则输出"YES"，否则输出"NO"。

样本输入：

3
2 1
10 10
3 2
1 2 2
3 2
1 2 3

样本输出：

YES
YES
NO

限制条件：

1 <= T <= 1000
2 <= n <= 100
1 <= K <= 10
0 <= a_i <= 1000

我已经用以下算法接受了我的解决方案---

a[i] is value in ith cell
n[i] is number of times it is selected in subset
T is total number of times the operation is done
=> a[i] - n[i] + (T - n[i])*K = 0 for all except 1
=> a[i]= n[i] (K+1) -TK 
=> a[i] = (K+1)(n[i]-T) + T

因此，除1（将变为零）和T除以K+1外，所有a[i]的余数都应该相同。我怀疑这个条件是必要的，但它怎么足够呢？

Answer 1

步骤1

想象一下，一个动作包括：

1. 选择由所有数字组成的子集a，其中a[i]>=K+1
2. 选择由整个集合K次组成的子集

子集A中的数字将减少K+1次，而集合A之外的数字将保持不变（增加K，然后减少K次）。

重复此步骤，直到所有数字都小于K+1。

这一步将改变数字，使其成为模K+1的余数。

步骤2

现在假设所有的数字都是相同的（除了1）。

我们现在可以选择由整个集合组成的子集（除了奇数集）。

这会将所有数字减少1（奇数除外）。重复此选择，直到我们一直减少到0。

结论

因此，如果所有数字（除了一个）都有模K+1的相同残差，我们可以使用步骤1将它们全部降低到相同的水平，然后使用步骤2将公共水平降低到0。