JZTXT

【每日一题】Problem 414B. Mashmokh and ACM

发布时间 2023-07-02 19:21:04作者: HelloEricy

原题

解决思路

  1. 先计算 \([1, n]\) 中的约数集合
  2. \(dp[i][j](i\in [1, n], j\in [1, k])\) 表示第 \(j\) 个数放置 \(i\) 所拥有的可能性
  3. 以此类推，到达 \(k\) 时，计算 \(\sum_{i=1}^{n}dp[i][k]\) 即可
#include <bits/stdc++.h>

int main() {
  int n, k; std::cin >> n >> k;
  std::map<int, std::vector<int>> m;
  m[0] = std::vector<int>(n + 1, 0);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
      if (i % j == 0) {
        if (m.find(i) == m.end()) m[i] = std::vector<int>();
        m[i].push_back(j);
      }
    }
    m[0][i] = i;
  }
  long long ans = 0;
  std::vector<std::vector<long long>> dp(
      n + 1, std::vector<long long>(k + 1, 0));
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= k; ++j) {
      if (j == 1) dp[i][j] = 1;
      else {
        for (auto &v : m[i]) {
          dp[i][j] += dp[v][j - 1];
          dp[i][j] %= 1000000007;
        }
      }
      if (j == k) {
        ans += dp[i][j];
        ans %= 1000000007;
      }
    }
  }

  std::cout << ans << std::endl;
  return 0;
}