ARC046 C - 掛け算

やり直し

C - 掛け算

解法

Bが10⁹乗なので愚直にシミュレーションするとTLEになってしまう。aを昇順に並び替えつつ、何回かシミュレーションをすると a[0] * A >= a[N-1] となる時が来る。こうなったらN周期で同じ列が現れる状態になる。周期的になるまでは高々N*log(max(a))回シミュレーションすれば良い。

周期的になる状態ができたら(残りB'回とする)あとはi < B' % Nを満たすa[i]はB'/N+1回、i >= B' % Nを満たすa[i]はB'/N回、Aをかければ良いとわかる。

愚直にAを掛け算するとTLEする可能性があるので、高速累乗すればACできる。

コード

#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>
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 int mod = 1e9 + 7;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N, A, B; cin >> N >> A >> B;
  ll a[N]; FOR(i,0,N) cin >> a[i];
  sort(a, a + N);
  if(A == 1) {
    FOR(i,0,N) cout << a[i] % mod << endl;
    return 0;
  }
  ll k = 0;
  while(B) {
    sort(a, a + N);
    if(a[0] * A >= a[N-1]) break;
    a[0] *= A;
    B--;
  }
  sort(a, a + N);
  // 周期的になる前に終わる
  if(B == 0) FOR(i,0,N) cout << a[i] % mod << endl;
  // 周期的になる
  else {
    FOR(i,0,N) a[i] %= mod;
    // B / N 回 A倍する
    FOR(i,B%N,N) {
      ll C = B / N;
      ll AA = A % mod;
      while(C) {
        if(C&1) a[i] = (a[i] * AA) % mod;
        AA = (AA * AA) % mod;
        C >>= 1;
      }
    }
    FOR(i,0,B%N) {
      ll C = B / N + 1;
      ll AA = A % mod;
      while(C) {
        if(C&1) a[i] = (a[i] * AA) % mod;
        AA = (AA * AA) % mod;
        C >>= 1;
      }
    }
    FOR(i,0,N) {
      cout << a[(i+B%N)%N] << endl;
    }
  }
  return 0;
}