AtCoder Regular Contest 051 C - 掛け算

問題

arc051.contest.atcoder.jp

解法

問題見た瞬間 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;
}