AtCoder ARC #051 : C - 掛け算

Convex Hull Trick未だに苦手。
http://arc051.contest.atcoder.jp/tasks/arc051_c

問題

N要素の整数列a[i]が与えられる。
a中一番小さい要素をA倍する、という処理を計B回行う。

その結果得られるaを昇順に並べ、10^9+7で割った余りを求めよ。

解法

a中の最小値と最大値の比がA未満になるまで、愚直にシミュレートしよう。
最大でも各項29回までしかA倍せずに上記の状態になる。

以降は１回A倍するとその要素は最大になるので、各要素は残りA倍回数を均等に振った値になる。
Nで割って余った分は小さい順に適用しておこう。

int N,A,B;
ll V[1010];
ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	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;
	
	cin>>N>>A>>B;
	FOR(i,N) cin>>V[i];
	sort(V,V+N);
	if(A==1) {
		FOR(i,N) cout<<V[i]<<endl;
		return;
	}
	while(B) {
		if(V[0]*A>V[N-1]) break;
		assert(V[0]*A/A ==V[0]);
		V[0]*=A;
		sort(V,V+N);
		B--;
	}
	
	FOR(i,N) {
		if(i>=(B%N)) _P("%lld\n",V[i]%mo * modpow(A,B/N) % mo);
	}
	FOR(i,N) {
		if(i<(B%N)) _P("%lld\n",V[i]%mo * modpow(A,B/N+1) % mo);
	}
}

まとめ

これはすんなり。でも1WAしてしまった…。