Codeforces #647 Div1 B. Johnny and Grandmaster

あんまりGrandmaster関係ないな。
http://codeforces.com/contest/1361/problem/B

問題

正整数Pに対し、非負整数K[i]を用いて(P^K[i])の形で表現できる整数列が与えられる。
この整数列を2つに分割し、総和の差の絶対値が最小になるようにしたとき、その値を求めよ。

解法

この問題は、各(P^K[i])に正か負かの符号を割り当て、総和の絶対値を0に近づける問題といえる。
そこで、K[i]の大きい順に、絶対値が小さくなる方向で割り当てていこう。

int T;
int N,P,K[1010101];
const ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&N,&P);
		FOR(i,N) scanf("%d",&K[i]);
		sort(K,K+N);
		
		if(P==1) {
			cout<<N%2<<endl;
			continue;
		}
		
		int pre=0;
		ll d=0;
		for(j=N-1;j>=0;j--) {
			if(d==0) {
				d++;
				pre=K[j];
			}
			else {
				while(pre>K[j]) {
					d=d*P;
					pre--;
					if(d>=1LL<<20) break;
				}
				if(d>=1LL<<20) {
					d%=mo;
					d=d*modpow(P,pre-K[j])%mo;
					d=(d+mo-1)%mo;
					for(i=j-1;i>=0;i--) {
						d=d*modpow(P,K[i+1]-K[i])%mo;
						d=(d+mo-1)%mo;
					}
					
					break;
				}
				else {
					d=(d+mo-1)%mo;
				}
				
			}
		}
		d=d*modpow(P,K[0])%mo;
		cout<<d<<endl;
	}
}

まとめ

Grandmasterに反応してしまう。