重複組み合わせには「数学的なもの」「蟻本的なもの」の2種類がある

数学的なもの

• nHrと表記されるもの
• https://mathtrain.jp/tyohukuc
• 例：{R, G, B}の玉が「無限に」あって、r個選ぶときの場合の数
• これはnCrが求められればいいのでn=10⁶程度まで求められる

蟻本的なもの

• n種類の物体がある
• i番目の物体は「Ai個」ある
• r個選ぶときの場合の数
• 蟻本v2 p67
• 計算量 O(nm)なのでn=10⁴までが限界

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～