【題解】Codeforces 1361B. Johnny and Grandmaster

#include <iostream>
#include <algorithm>
using namespace std;
 
int t, n, p, k[1000005], mod = 1e9+7;
long long delta, ans;
 
long long pm(int x){
    long long ret = 1;
    long long now = p;
    while (x){
        if (x & 1){
            ret *= now;
            ret %= mod;
        }
        now *= now;
        now %= mod;
        x >>= 1;
    }
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--){
        cin >> n >> p;
        for (int i = 0; i < n; i++){
            cin >> k[i];
        }
        sort(k, k+n);
        delta = 1;
        ans = pm(k[n-1]);
        for (int i = n-2; i >= 0; i--){
            if (k[i] != k[i+1] && delta && p!=1){
                for (int j = k[i+1]-k[i]; j > 0; j--){
                    if (delta > n) break;
                    delta *= p;
                }
            }
            if (delta == 0){
                delta++;
                ans += pm(k[i]);
                ans %= mod;
            }
            else{
                delta--;
                ans -= pm(k[i]);
                ans += mod;
                ans %= mod;
            }
        }
        cout << ans << "\n";
    }
}