摘要：
目前（洛谷）最优解写法。由于每个式子都是形如\的形式，即底数相同，可以考虑变成\(p\)进制，发现对于任意\和\，满足\时，\一定被\整除。我们可以考虑记录\表示两堆的和，使任意时刻\。考虑\降序排序时贪心用较大的\(k\)补足\。\当前到\(i\)，且\。否则先使\，再用剩下的\分配给\，注意满足\。
目前（洛谷）最优解写法。
首先将 \(k_i\) 降序排列，并将相同的 \(k_i\) 合并。由于每个式子都是形如 \(p^{k_i}\) 的形式，即底数相同，可以考虑变成 \(p\) 进制，发现对于任意 \(c_1,\, \ldots ,\, c_{i+1}\) 和 \(a_0 < a_1 < a_2 \ldots < a_{i+1}\)，满足 \(c_{i+1} \times p^{a_{i+1}} \ge \sum\limits_{j=1}^i c_{j} \times p_{a_j}\) 时，\(c_{i+1} \times p^{a_{i+1}} - \sum\limits_{j=1}^i c_{j} \times p_{a_j}\) 一定被 \(p^{a_0}\) 整除。
我们可以考虑记录 \(s1,\,s2\) 表示两堆的和，使任意时刻 \(s1 < s2\)。
考虑 \(k_i\) 降序排序时贪心用较大的 \(k\) 补足 \(s2-s1\)。\(\text{now}\) 当前到 \(i\)，且 \(p^{k_i} \times \text{now} = s2 - s1\)。由于是降序排序，如果 \(\text{now} > n\) 那么后面的 \(k\) 都一定分配到 \(s1\)。否则先使 \(s1=s2\)，再用剩下的 \(k_i\) 分配给 \(s1,s2\)，注意满足 \(s1<s2\)。
\(\text{Code}\)：
def(N, int, 1e6 + 5)
def(p, int, 1e9 + 7)
int n, m;
int k[N];
int main() {
int t; qread(t);
W(t) {
qread(n, m);
rep(i, 1, n) qread(k[i]);
sort(k + 1, k + n + 1, greater<int>());
ll nw = 0;
ll s1 = 0, s2 = 0;
rep(i, 1, n) {
if(nw && m != 1 && i != 1) {
int nwm = k[i - 1] - k[i];
rep(j, 1, nwm) {
nw *= m;
if(nw > n) {
rep(l, i, n) s1 = (s1 + qpow(k[l], m, p)) % p;
goto End;
}
}
}
int cn = 0, j = i;
while(j <= n && k[i] == k[j]) ++j, ++cn;
int ps = min(nw, (ll)cn); nw -= ps;
if(cn > ps) {
cn -= ps;
int c1 = cn >> 1, c2 = cn - c1;
if(c1 != c2) nw = 1;
s1 = qpow(k[i], m, p) * c1 % p;
s2 = qpow(k[i], m, p) * c2 % p;
}
else s1 = (s1 + qpow(k[i], m, p) * cn % p) % p;
i = j - 1;
// cout << s1 << ' ' << s2 << endl;
}
End:;
printf("%lld\n", (s2 - s1 + p) % p);
}
return 0;
}