Partition Table(分割数テーブル) (math/combinatorics/partition-table.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-05-01 23:44:47+09:00
• Include: #include "math/combinatorics/partition-table.hpp"

概要

分割数 $P(n, k)$ は整数 $n$ をちょうど $k$ 個の非負整数の和で表す方法の数を与える. 順序が異なるものは同一視する.

• partition_table(n, k): 各 $i \leq n, j \leq k$ に対し分割数 $P(n, k)$ を求める.

計算量

• $O(nk)$

Verified with

• test/verify/aoj-dpl-5-j.test.cpp

Code

/**
 * @brief Partition Table(分割数テーブル)
 *
 */
template <typename T>
vector<vector<T> > partition_table(int n, int k) {
  vector<vector<T> > dp(n + 1, vector<T>(k + 1));
  dp[0][0] = 1;
  for (int i = 0; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
      if (i - j >= 0)
        dp[i][j] = dp[i][j - 1] + dp[i - j][j];
      else
        dp[i][j] = dp[i][j - 1];
    }
  }
  return dp;
}

#line 1 "math/combinatorics/partition-table.hpp"
/**
 * @brief Partition Table(分割数テーブル)
 *
 */
template <typename T>
vector<vector<T> > partition_table(int n, int k) {
  vector<vector<T> > dp(n + 1, vector<T>(k + 1));
  dp[0][0] = 1;
  for (int i = 0; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
      if (i - j >= 0)
        dp[i][j] = dp[i][j - 1] + dp[i - j][j];
      else
        dp[i][j] = dp[i][j - 1];
    }
  }
  return dp;
}

Back to top page