E. Johnny and Grandmaster

 

题意：有n个数a[i]，要分成两堆，每堆的和为 ∑pa[i]\sum p^{a[i]}，两堆的差值最小，问差值。

贪心

首先要发现进制数的性质，对于任意一个i，∑j=1i−1pa[j]\sum_{j=1}^{i-1}p^{a[j]} 要么小于 pa[i]p^{a[i]}，要么存在一个 k，使得 ∑j=ki−1pa[j]=pa[i]\sum_{j=k}^{i-1}p^{a[j]}=p^{a[i]}，且不论k是个怎么样的数组，都成立。

从大到小排列，每次看如果左边多了，就放右边，否则就放左边。

然后就可以分类讨论贪心的正确性了。下面为了方便，直接用 a[i]a[i] 代替 pa[i]p^{a[i]}。

如果 ∑i=1n−1a[i]<a[n]\sum_{i=1}^{n-1}a[i]<a[n] ，则一定是先把最大的放一堆，其他都放另一堆。

假设现在有 a[n]=∑i=kn−1a[i]a[n]=\sum_{i=k}^{n-1}a[i]，则用这些可以凑出两堆差值为0。还有多出来一些。

再假设多出来的这些不能凑出两堆差值为0。

先考虑多出来一个，考虑如果把多的那个和已经凑好的某个交换，由于贪心策略，多的那个一定是最小的，所以交换之后小的那堆变小了，大的那堆变大了，差值增加。

如果多出来两个，就显然了。

如果多出来三个，贪心就是两个放一堆，最大的放另一堆，且两个的那堆小于一个的那堆。这时可能会想，如果把小的那堆中的一个和另一堆某个大的交换，是不是可能补上差值？然而并不是。假设和之前刚放进去的那个大的交换，本来是 p3−p2−p2p^3-p^2-p^2，现在变成 p3+p1−p2p^3+p^1-p^2，差值反超，反而更大了。而刚放进去的那个是那堆最小的，和最小的交换都使差值变大，何况和其它更大的交换。

再多出来更多的就类似了。

而如果假设多出来的还能凑出两堆差值为0，那么把这两次并在一起，差值还为0，问题就和上一个一样了。

所以，遇到进制问题，先考虑贪心就完事了。要相信幂次的增长速度是很大的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
const ll mod = 1e9 + 7, mod2 = 1e8 + 7;
int T;
ll n, p;
ll a[N];
ll Pow(ll a, ll b, ll mod) {
	ll res = 1ll;
	while (b) {
		if (b & 1)res = res * a%mod;
		a = a * a%mod;
		b >>= 1;
	}
	return res;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld", &n, &p);
		for (int i = 1; i <= n; i++) {
			scanf("%lld", &a[i]);
		}
		sort(a + 1, a + n + 1, greater<ll>());
		ll ans = 0, tmp = 0;
		for (int i = 1; i <= n; i++) {
			if (!ans && !tmp) {
				ans = (ans + Pow(p, a[i], mod)) % mod;
				tmp = (tmp + Pow(p, a[i], mod2)) % mod2;
			}
			else {
				ans = (ans - Pow(p, a[i], mod) + mod) % mod;
				tmp = (tmp - Pow(p, a[i], mod2) + mod2) % mod2;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}