Submission #6237059


Source Code Expand

Copy
#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

Submission Time
Task F - Small Products
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2500 Byte
Status
Exec Time 318 ms
Memory 103688 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 600 / 600 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 318 ms 103688 KB
02.txt 269 ms 88224 KB
03.txt 278 ms 91040 KB
04.txt 293 ms 95776 KB
05.txt 127 ms 41480 KB
06.txt 1 ms 256 KB
09.txt 277 ms 90944 KB
10.txt 1 ms 256 KB
11.txt 99 ms 32588 KB
12.txt 90 ms 29772 KB
13.txt 77 ms 25548 KB
14.txt 1 ms 256 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 65 ms 22240 KB