Luzhiled's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ei1333/library

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

概要

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

計算量

Verified with

Code

/**
 * @brief Partition Table(分割数テーブル)
 * @docs docs/partition-table.md
 */
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(分割数テーブル)
 * @docs docs/partition-table.md
 */
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