yukicoder No.856 - 増える演算

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLay（version 20190820-1）のコード

C++に変換後のコードはこちら

int N, A[1d5];

double c[100001], cnv[200001];
ll s[100001];
int mn[100001];
{
  int i;
  ll tk;
  mint res, tmp;
  double dmin, dtmp;

  rd(N,A(N));

  res = 1;
  
  rep(i,N) c[A[i]]++;
  convolution(c, 100001, cnv, 200001);
  rep(i,N) cnv[2A[i]]--;

  rep(i,200001){
    tk = (ll)(cnv[i]/2 + 0.5);
    if(tk) res *= (mint(i) ** tk);
  }

  for(i=N-1;i>=0;i--) s[i] = s[i+1] + A[i];
  rep(i,N) res *= (mint(A[i]) ** s[i+1]);

  mn[N] = int_inf;
  for(i=N-1;i>=0;i--) mn[i] = min(mn[i+1], A[i]);

  dmin = 1e300;
  for(i=N-2;i>=0;i--){
    dtmp = log(A[i] + mn[i+1]) + log(A[i]) * mn[i+1];
    if(dtmp < dmin){
      dmin = dtmp;
      tmp = (A[i] + mn[i+1]) * ( mint(A[i]) ** mn[i+1] );
    }
  }

  res /= tmp;
  wt(res);
}

Current time: 2024年04月20日03時49分14秒
Last modified: 2019年08月21日06時07分33秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)