ARC051 C - 掛け算

解法

愚直にシミュレーションするとB≦10⁹なのでTLEしてしまう。

操作を十分な回数行うと、一番小さい数にAをかけると一番大きな数になる状態ができる。

この状態になれば周期性を利用してとくことができる。

この状態になった時の数列が{a'}で残りの操作回数がB'回の時、

i = B' % N とすると、

a'_0 ~ a'_{i-1} は B' / N + 1 回、

a'_i ~ a'_{N-1} は B' / N 回

Aをかける。

愚直にAをかけるとTLEなのでダブリングを用いる。

出力は a'_i, ..., a'_{N-1}, a'_0, ... , a'_{i-1}の順ですれば良い。

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
const ll MOD = 1000000007;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N, A, B; cin >> N >> A >> B;
  ll a[N];
  priority_queue<ll, vector<ll>, greater<ll> > Q;
  FOR(i,0,N) {
    cin >> a[i];
    Q.push(a[i]);
  }
  sort(a, a + N);
  if(A == 1) {
    FOR(i,0,N) cout << a[i] % MOD << endl;
    return 0;
  }
  while(Q.top() < a[N-1]) {
    B--;
    ll q = Q.top(); Q.pop();
    Q.push(q * A);
    if(B == 0) break;
  }
  FOR(i,0,N) {
    a[i] = Q.top();
    Q.pop();
  }
  if(B == 0) {
    FOR(i,0,N) cout << a[i] % MOD << endl;
    return 0;
  }
  // 残りB回N回周期
  FOR(i,0,N) {
    int j = (i + B % N) % N;
    ll x = a[j] % MOD;
    ll t = j < B % N ? B / N + 1 : B / N;
    ll AA = A % MOD;
    // ダブリング
    while(t) {
      if(t & 1) x = (x * AA) % MOD;
      AA = (AA * AA) % MOD;
      t >>= 1;
    }
    cout << x << endl;
  }
  return 0;
}