説明

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

計算量

  • $O(nk)$

実装例

  • get_partition($n$, $k$):= 各 $i \leq n, j \leq k$ に対し分割数 $P(n, k)$ を求め、それを返す。
template< typename T >
vector< vector< T > > get_partition(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;
}

検証

AOJ DPL_5_J ボールと箱 10

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_5_J"

#include "../../template/template.cpp"

#include "../mod-int.cpp"

#include "../partition-table.cpp"

int main() {
  int N, K;
  cin >> N >> K;
  cout << get_partition< modint >(N, K)[N][K] << endl;
}