Submission #6237059

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;
using namespace std;

ll N, K;
ll M = 1000000007;
vector<ll> gids; // グループID一覧
vector<ll> sizes; // gid_ix => グループの要素数
vector<vector<ll>> dp; // dp[i][gid_ix]: i個の並べた時に、最後の数が gid に属する
vector<vector<ll>> memo;

ll f (ll i, ll gid_ix) {
  //if (gid_ix >= gids.size())
  //  return 0;
  auto gid = gids[gid_ix];
  // static map<PLL, ll> memo;
  //if (memo.find(make_pair(i, gid_ix)) != memo.end())
  //  return memo[make_pair(i, gid_ix)];
  if (memo[i][gid_ix] != -1)
    return memo[i][gid_ix];

  // cout<<"gid="<<gid<<endl;
  ll res;
  if (i == 0)
    res = 0;
  else if (gid == 0)
    res = 0; // need?
  else if (gid == N)
    res =  dp[i][gids.size()-1];
  else
    res = f(i, gid_ix+1) + (dp[i][gid_ix] * sizes[gid_ix]) %M;

  // cout<<"i="<<i<<" gid="<<gid<<endl;
  res %= M;
  return memo[i][gid_ix] = res;
}

signed main() {
  cin >> N >> K;

  for (int x = 1; x * x <= N; x++) {
    gids.push_back(x);
    gids.push_back(N/x);
  }
  sort(begin(gids), end(gids));
  gids.erase(unique(begin(gids), end(gids)), end(gids));
  sizes.resize(gids.size());
  // cout<<"max gid="<<gids[gids.size()-1]<<endl;

  for (int i = 0; i < gids.size()-1; i++) {
    sizes[i] = N/gids[i] - N/gids[i+1];
    sizes[i] %= M;
  }
  sizes[gids.size()-1] = 1;

  // for (auto p: sizes) {
  //   cout<<"gid="<<p.first<<" size="<<p.second<<endl;
  //   cout<<"gid="<<p.first<<" next_gid="<<next_gid[p.first]<<endl;
  // }

  // cout<<"gids.size()="<<gids.size()<<endl;
  dp.resize(K+1, vector<ll>(gids.size()+1));
  memo.resize(K+1, vector<ll>(gids.size()+1, -1));
  for (int gid_ix = 0; gid_ix < gids.size(); gid_ix++) {
    dp[1][gid_ix] = 1;
    // printf("dp[%d][%d] = %d\n", 1, gid, dp[1][gid]);
  }
  for (int i=2; i<=K; i++) {
    // for (int x = 1; x <= N; x++) {
    // for (auto gid: gids) {
    for (int gid_ix=gids.size()-1; gid_ix>=0; gid_ix--) {
      auto gid = gids[gid_ix];
      dp[i][gid_ix] = f(i-1, gids.size()-1 - gid_ix) %M;
      // printf("dp[%d][%d] = %d\n", i, x, dp[i][x]);
    }
  }

  ll ans = 0;
  for (int gid_ix = 0; gid_ix < gids.size(); gid_ix++) {
    auto gid = gids[gid_ix];
    ans += (dp[K][gid_ix] * sizes[gid_ix])%M;
    ans %= M;
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result