AtCoder Regular Contest 051 C - 掛け算
解法
まず数列の最大値を超えないギリギリまで愚直にシミュレートする。
ここは(楽をして)priority_queueを使った。
このシミュレートは、数列の最大値をXとすると、 しかかからない。
ここまでやると、どの要素をA倍しても最大値になる状態になる。
これは数列全体を何倍しても保たれる性質なので、A倍しなきゃいけない残りの回数がN以下になるまで、繰り返し二乗法を使って一気に進める。
残った端数分の回数は、素直に小さい要素から順にかける。
繰り返し二乗法部分はなので、全体で。
A=1のケースに注意する。
実装
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> using namespace std; #define int long long const int MOD = 1000000007; int N, A, B, C[50]; int Pow(int x, int n) { if (n == 0) return 1; return Pow(x*x % MOD, n/2)*((n&1) ? x : 1) % MOD; } void Solve() { if (A == 1) { sort(C, C + N); return; } priority_queue< int, vector<int>, greater<int> > pq; int ma = 0; for (int i = 0; i < N; i++) { ma = max(ma, C[i]); pq.push(C[i]); } while (B > 0 && pq.top()*A <= ma) { int t = pq.top(); pq.pop(); pq.push(t*A); B--; } for (int i = 0; i < N; i++) { int k = B/N; if (i < (B % N)) k++; C[(N - B % N + i) % N] = pq.top()*Pow(A, k) % MOD; pq.pop(); } } signed main() { cin >> N >> A >> B; for (int i = 0; i < N; i++) { cin >> C[i]; } Solve(); for (int i = 0; i < N; i++) { printf("%lld\n", C[i]); } return 0; }