 The Double Dixie Cup Problem典型的な「クーポンコレクター問題」は、「N種類のクーポンが1枚ずつ入った箱がある。箱からクーポンを1枚引いて、そのたびに同じ種類のクーポンが箱に戻される試行を繰り返した時、N種類全て1枚以上引くまでの試行回数の期待値はいくつか」という問題で、この回答は有名です。

The Double Dixie Cup Problemとは、これを「N種類全て2枚以上引くまでの試行回数」や「N種類全てM枚以上引くまでの試行回数」に一般化した問題です。
例えば「保存用に2枚ずつ欲しい」とか、「必要に応じてトレードすることで、友だち2人でコンプリートしたい」みたいなシチュエーションはよくありますね。
本スクラップでは、これを動的計画法（期待値DP）を使って求めます。N^M≦10^8くらいなら求まるので、実用上は十分でしょう。
また、クーポンコレクター問題の別の拡張として
N種類のクーポンが出る確率がそれぞれ違う（A賞が5%, E賞が55%出るクジなど）
期待値でなく「90%以上コンプできる回数」などが知りたい

に言及します。

 期待値DP以外について
 閉じた式あるのですが、大変です。

Deep Researchが教えてくれた参考文献

https://chatgpt.com/share/67b5ba9f-ba5c-800e-8cb5-a1b5c1a16e81

 自明な上界例えばN=7, M=1の時は18.15回なので、N=7, M=2の場合は明らかに36.3回以下ですね。

実際はN=2, M=1の時は29.42回なので、そこそこ乖離はありますが。

 シミュレーション適当に1万回くらいシミュレーションすればそこそこ収束すると思うので、それでもいいです。

binomialsheep

 例7種類で等確率のクーポンを2枚ずつ揃えたい場合の試行回数の期待値。
dp[a][b]を「2枚揃ったクーポンがa種類、1枚揃ったクーポンがb種類、0枚揃ったクーポンが7-a-b種類の状態から、7種類が2枚ずつ揃う状態までの試行回数の期待値」とする（題意に沿わないa, bに対しては定義しない）
定義より、dp[7][0] = 0
0枚揃ったクーポンを引いてdp[a][b+1]に遷移できる確率p_0は(7-a-b)/7
1枚揃ったクーポンを引いてdp[a+1][b-1]に遷移できる確率p_1はb/7
2枚揃ったクーポンを引いてdp[a][b]に留まる確率p_2はa/7

dp[0][0]が求めたい期待値

である。

これをそのまま漸化式で表すと、

dp[a][b] :=
\begin{cases} 
  0, & \text{if } a = 7, b = 0, \\
  1 + p_0 dp[a][b+1] + p_1 dp[a+1][b-1] + p_2 dp[a][b], 
  & \text{if } 0 \leq a, 0 \leq b, a + b \leq 7, \\
  0, & \text{otherwise}.
\end{cases}
となる。 式変形して右辺からdp[a][b]を消すと、

dp[a][b] :=
\begin{cases} 
  0, & \text{if } a = 7, b = 0, \\
  \frac{1 + p_0 dp[a][b+1] + p_1 dp[a+1][b-1]}{1-p_2}, 
  & \text{if } 0 \leq a, 0 \leq b, a + b \leq 7, \\
  0, & \text{otherwise}.
\end{cases}
これをそのままプログラムに落として実行すれば求まる（29.4247回）
#include <bits/stdc++.h>
using namespace std;

int main() {
  vector dp(8, vector<double>(8));
  for (int a = 7; a >= 0; a--) {
    for (int b = 7 - a; b >= 0; b--) {
      if (a == 7 && b == 0) {
        dp[7][0] = 0;
        continue;
      }
      double p0 = (7 - a - b) / 7., p1 = b / 7., p2 = a / 7.;
      dp[a][b] = 1;
      // 0個揃ったものが1個揃う
      if (b < 7) dp[a][b] += p0 * dp[a][b + 1];
      // 1個揃ったものが2個揃う
      if (a < 7 && b >= 1) dp[a][b] += p1 * dp[a + 1][b - 1];
      // 2個揃ったものが被る
      dp[a][b] /= 1 - p2;
    }
  }
  cout << dp[0][0] << endl;
  return 0;
}
実装上はメモ化再帰の方が簡単かも。

 DPが分からない人向けhttps://atcoder.jp/contests/dp

 期待値DPが分からない人向けhttps://atcoder.jp/contests/abc184/tasks/abc184_d

 期待値DPの自己ループ除去が分からない人向けhttps://atcoder.jp/contests/abc333/tasks/abc333_f

 状態の持ち方が天才だと思った人向けhttps://atcoder.jp/contests/dp/tasks/dp_j

binomialsheep

N種類のクーポンが出る確率がそれぞれ違う場合

状態をまとめられないので、計算量は悪化するが別の次元に持てばDP自体は簡単。
例えば「A賞が2種類でそれぞれ1%、B賞が3種類でそれぞれ2%……」のような問題で1個ずつ揃えたい場合は、
dp[a][b][c][d][e] := A賞がa枚、B賞がb枚、C賞がc枚、D賞がd枚、E賞がe枚ある状態からコンプリートまでに引く枚数の期待値
にして、同じA賞でも既に持っているやつを引いたかまだ持っていないやつを引いたかで分岐すればそれなりにまとまる。
さらに2個ずつ揃えたい場合はもっと次元が増える。

binomialsheep

期待値でなく「90%以上コンプできる回数」などが知りたい

こっちの方が簡単。全状態の確率を持って、普通にDPする。
dp[i][a][b] := i回引いて、2枚引いたのがa種類、1枚引いたのがb種類の確率
（いわゆるnext dpで1次元目は潰せるが）