B. Johnny and Grandmaster 思维+hash

B. Johnny and Grandmaster 思维+hash

题目大意：

题目意思就是给一个长度为n的序列k ， 然后呢要求将这些数分为两个集合A、B,使得两个集合差值的绝对值最小，也就是 \(min|\sum{p^{k_i}}-\sum{p^{k_j}}|\)

题解：

这个想到了就是一个简单的思维题，再加一点点哈希，但是不经过仔细思考，对代码构成的思考、代码量的思考和难写程度，那么这个就会成为一个恶心的模拟题。

我就写成了模拟题，bug现在还没有找出来，所以我放弃了，看了题解。

题解的思路很简单也很巧妙：

• 首先对这个序列按照降序进行排序
• 然后对于一个大一点的数 \(p^x\) 要么他就是可以被后面的数凑出来，要么不行
• 如果可以凑出来，那么一直减下去就会变成0
• 如果不可以，那么答案就是这个数减去后面的所有的数
• 那么哪里要用到hash呢？
• 这个是因为\(p^x\) 可能成为模数的倍数，那么也会变成0，所以要用双哈希的思想判断这个不是0，所以再取一个模数。

如果wa了，那么很可能是模数有问题。。。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
const int mod1 = 1e9+7;
const int mod2 = 983231753;
int a[maxn];
typedef long long ll;
ll binpow(ll x,ll k,ll mod){
	ll ans = 1;
	x%=mod;
	while(k){
		if(k&1) ans = ans*x%mod;
		x=(x*x)%mod;
		k>>=1;
	}
	return ans;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n,p;
		scanf("%d%d",&n,&p);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		sort(a+1,a+1+n);
		ll ans1 = 0,ans2 = 0;
		for(int i=n;i>=1;i--){
			ll tmp1 = binpow(p,a[i],mod1),tmp2 = binpow(p,a[i],mod2);
			if(ans1==0&&ans2==0) ans1 = tmp1,ans2 = tmp2;
			else{
				ans1 = (ans1 - tmp1 + mod1)%mod1;
				ans2 = (ans2 - tmp2 + mod2)%mod2;
			}
		}
		printf("%lld\n", ans1);
	}
	return 0;
}

B. Johnny and Grandmaster 思维+hash

原文：https://www.cnblogs.com/EchoZQN/p/13618618.html