perogram

No.269 見栄っ張りの募金活動 ~分割数~

f:id:peroon:20190731072803j:plain

n個の互いに区別できない品物を、m個以下に分割する方法の総数をnのm分割と言い、m=nのとき特にnの分割数と言う。

Quiz

https://yukicoder.me/problems/no/269

AC Code

https://yukicoder.me/submissions/364228

解法

  • 先にK円ずつ増えていく分を徴収する
  • 残ったお金を分割数で分ける

分割数クラス

  • 蟻本v2 p66を参考に自作した
// 分割数 n個のものをm個以下に分割する
// 蟻本v2 p66
struct PartitionFunction{
    vector<vector<ll>> dp; //dp[M][N]
    ll N = -1;
    ll M = -1;
    void init(ll n, ll m){
        N = n;
        M = m;
        // 大きめに確保
        dp.resize(M+5);
        REP(i, M+5){
            dp[i].resize(N+5, 0);
        }
        prepare();
    }
    void prepare(){
        dp[0][0] = 1;
        FOR(i, 1, M+1){
            FOR(j, 0, N+1){
                if(j-i>=0){
                    dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % mod;
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
    }
    ll f(ll n, ll m){
        return dp[m][n];
    }
};