AtCoder Regular Contest 051 C - 掛け算
解法
問題見た瞬間 KitayutaMart に似てると思ったんですけど Twitter 見る感じあんまりそういう感想を持った人がいなかったようです。
mayokoex.hatenablog.com
ただ, この問題の発想のベースは使えます。数列 a を小さい順にソートした時, a[0]*A > a[N-1] が成り立っていたとすると, あとは
- a[0] を A 倍して, これを新しく a[N-1] にする
- a[0] <- a[1], ..., a[N-2] <- a[N-1] と移動させる
という単純作業でできます。これは周期 N の操作になっているので, B が大きい場合も間に合います。
コーナーケースは A = 1 の時です。この場合は永遠に a[0]*A > a[N-1] が成り立たないことがあるのですぐに配列を出力します。
ll mod_pow(ll x, ll p, ll MOD) { ll a = 1; while (p) { if (p%2) a = a*x%MOD; x = x*x%MOD; p/=2; } return a; } const int MOD = 1e9+7; void print(const vector<ll>& a) { for (ll el : a) cout << el << endl; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; ll A, B; cin >> N >> A >> B; vector<ll> a(N); for (int i = 0; i < N; i++) cin >> a[i]; if (A==1) { sort(a.begin(), a.end()); print(a); return 0; } while (B > 0) { sort(a.begin(), a.end()); if (a[0]*A > a.back()) break; a[0] *= A; B--; } sort(a.begin(), a.end()); if (!B) { print(a); return 0; } ll num = B/N; int extra = B%N; for (int i = 0; i < extra; i++) { a[i] %= MOD; a[i] = a[i]*mod_pow(A, num+1, MOD); a[i] %= MOD; } for (int i = extra; i < N; i++) { a[i] %= MOD; a[i] = a[i]*mod_pow(A, num, MOD); a[i] %= MOD; } vector<ll> ans; for (int i = extra; i < N; i++) ans.push_back(a[i]); for (int i = 0; i < extra; i++) ans.push_back(a[i]); print(ans); return 0; }