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

ライブラリ

分割数の定義

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

// 例
5の分割数は、7。なぜならば、

1,1,1,1,1
2,1,1,1
3,1,1
2,2,1
4,1
3,2,
5

の7種類があるから

※1,3,1 == 3,1,1のように同一視（箱は区別しない）するので数えるのが難しい

英語ではpartition functionという
f(5) = 7

Quiz

AC

解法

  • 先にK円ずつ増えていく分を徴収する
  • 残ったお金を分割数で分ける
    • なぜそれでよい？→5人いて余りのお金が10円として、例えば3分割したとき、分割された数列はソート済みのものを数えるとして、例えば2,3,5に分割されたとき、最後の人から大きい順に割り当てれば条件を満たすため（5人に0,0,2,3,5円をそれぞれ追加）

分割数クラス

  • 蟻本v2 p66を参考に自作した
// using ll = long long;
// #define FOR(i,a,b) for(ll i=(a);i<(b);++i)

// 分割数 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];
    }
};

計算量

  • O(NM)

verified✅