combinatorics/partitiontable.cpp

• View this file on GitHub
• Last update: 2020-10-27 13:13:52+09:00

Verified with

• test/aoj/DPL_5_J.test.cpp
• test/aoj/DPL_5_L.test.cpp

Code

#ifndef call_from_test
#include <bits/stdc++.h>
using namespace std;
#endif

//BEGIN CUT HERE
template<typename M>
struct PartitionTable{
  vector< vector<M> > dp;
  PartitionTable(int h,int w):dp(h+1,vector<M>(w+1,0)){
    dp[0][0]=M(1);
    for(int i=0;i<=h;i++){
      for(int j=1;j<=w;j++){
        dp[i][j]=dp[i][j-1];
        if(i-j>=0) dp[i][j]+=dp[i-j][j];
      }
    }
  }

  // put n identical balls into k identical boxes
  M operator()(int n,int k){return dp[n][k];}

  // put n identical balls into some boxes
  M operator()(int n){return dp[n][n];}
};
//END CUT HERE

#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#line 1 "combinatorics/partitiontable.cpp"

#include <bits/stdc++.h>
using namespace std;
#endif

//BEGIN CUT HERE
template<typename M>
struct PartitionTable{
  vector< vector<M> > dp;
  PartitionTable(int h,int w):dp(h+1,vector<M>(w+1,0)){
    dp[0][0]=M(1);
    for(int i=0;i<=h;i++){
      for(int j=1;j<=w;j++){
        dp[i][j]=dp[i][j-1];
        if(i-j>=0) dp[i][j]+=dp[i-j][j];
      }
    }
  }

  // put n identical balls into k identical boxes
  M operator()(int n,int k){return dp[n][k];}

  // put n identical balls into some boxes
  M operator()(int n){return dp[n][n];}
};
//END CUT HERE

#ifndef call_from_test
signed main(){
  return 0;
}
#endif

Back to top page