AtCoder Beginner Contest #132 F問題 - Small Products

Source

AtCoder Beginner Contest #132
問題文

問題概要

省略

解法

省略

cLay（version 20190630-1）のコード

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

int N, K;
int m[100000], s;
mint dp[100000], sm[100000], c[100000];
{
  int i, j, k;
  mint res;
  rd(N,K);

  i = 1;
  while(i <= N){
    k = bsearch_max[int,k,i,N](N/i <= N/k);
    m[s] = i;
    c[s] = k-i+1;
    s++;
    i = k+1;
  }

  rep(i,s) dp[i] = c[i];
  rep(K-1){
    sm[0] = 0;
    rep(i,s) sm[i+1] = sm[i] + dp[i];

    j = s-1;
    rep(i,s){
      while(j >= 0 && m[i] * m[j] > N) j--;
      dp[i] = sm[j+1] * c[i];
    }
  }

  res = 0;
  rep(i,s) res += dp[i];
  wt(res);
}

Current time: 2024年04月26日07時02分19秒
Last modified: 2019年06月30日02時46分19秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC132 ABC_F
トップページに戻る

Logged in as: unknown user (not login)