分割数を三通りの方法で求めるやつ

はい

#include "bits/stdc++.h"

// space: O(n^2), time: O(n^3)
// n ~ 2000
class PartitionNumberN3 {
  using ll = long long;
  ll rec(ll n, ll k) {
    if (dp[n][k] != -1) return dp[n][k];
    ll ret = 0;
    for (ll i = 0; i <= k; i++)
      ret += rec(n - k + i, std::min(n - k + i, k - i));
    return dp[n][k] = ret % MOD;
  }
public:
  const ll MOD = 1000000007;
  ll n;
  ll** dp; // dp[n][k]: n を k 以下の和で表す場合の数
  PartitionNumberN3(ll n) : n(n) {
    dp = new ll*[n + 1];
    for (ll i = 0; i <= n; i++) dp[i] = new ll[n + 1];
    for (ll i = 0; i <= n; i++) for (ll j = 0; j <= n; j++) dp[i][j] = -1;
    for (ll i = 0; i <= n; i++) dp[0][i] = 1;
    for (ll i = 1; i <= n; i++) dp[i][0] = 0;
    rec(n, n);
  }
  ~PartitionNumberN3() {
    for (ll i = 0; i <= n; i++) delete[] dp[i];
    delete[] dp;
  }

  ll getAns() {
    return dp[n][n];
  }
};

// space: O(n^2), time: O(n^2)
// n ~ 20000
class PartitionNumberN2 {
  using ll = long long;
public:
  const ll MOD = 1000000007;
  ll n;
  ll** dp; // dp[n][k]: n を k 個以下に分割する場合の数
  PartitionNumberN2(ll n) : n(n) {
    dp = new ll*[n + 1];
    for (ll i = 0; i <= n; i++) dp[i] = new ll[n + 1];
    for (ll i = 0; i <= n; i++) dp[i][0] = 0;
    for (ll i = 0; i <= n; i++) dp[0][i] = 1;
    for (ll i = 1; i <= n; i++) for (ll j = 1; j <= n; j++)
      dp[i][j] = (dp[i][j - 1] + (i >= j ? dp[i - j][j] : 0)) % MOD;
  }
  ~PartitionNumberN2() {
    for (ll i = 0; i <= n; i++) delete[] dp[i];
    delete[] dp;
  }

  ll getAns() {
    return dp[n][n];
  }
};

// https://en.wikipedia.org/wiki/Pentagonal_number_theorem
// space: O(n), time: O(n sqrt(n))
// n ~ 1000000
class PartitionNumberNsqrtN {
  using ll = long long;
  inline ll gp(ll k) { return k * (3 * k - 1) / 2; }
public:
  const ll MOD = 1000000007;
  ll n;
  ll* p;
  PartitionNumberNsqrtN(ll n) : n(n) {
    p = new ll[n + 1];
    p[0] = 1;
    ll maxcnt = 0;
    for (ll i = 1; i <= n; i++) {
      p[i] = 0;
      for (ll j = 1;; j += 2) {
        ll k = gp(j); if (k > i) break;
        p[i] += p[i - k];
        k = gp(-j); if (k > i) break;
        p[i] += p[i - k];
        k = gp(j + 1); if (k > i) break;
        p[i] -= p[i - k];
        k = gp(-j - 1); if (k > i) break;
        p[i] -= p[i - k];
      }
      p[i] %= MOD;
    }
  }
  ~PartitionNumberNsqrtN() {
    delete[] p;
  }

  ll getAns() {
    return (p[n] + MOD) % MOD;
  }
};

int main() {
  using ll = long long;
  ll N = 1000;

  PartitionNumberN3 pn1(N);
  PartitionNumberN2 pn2(N);
  PartitionNumberNsqrtN pn3(N);

  std::cout << pn1.getAns() << std::endl;
  std::cout << pn2.getAns() << std::endl;
  std::cout << pn3.getAns() << std::endl;

  return 0;
}