以下、第二種スターリング数を \(S(n,k)\) で表します。また、期待値を直接求めるのではなく、\(A\) として考えられるもの全体に対する \(\mathrm{mex}\) の総和を求めることにします。

以下の操作を考えます。

\(0,1,\dots,M\) と番号のついた \(M+1\) 個の箱が横一列に並んでいる。\(1,2,\dots,N\) と番号のついたボールを、箱 \(M\) を除く \(M\) 個の箱に分配する。その後、空の箱のうち最も番号の小さいものよりも小さい番号の箱を一つ選び、その箱のボールをすべて箱 \(M\) に移す。

この操作の個数が求めるべき総和と一致します。

この操作は逆操作を考えると次のように言い換えることが出来ます。

\(0,1,\dots,M\) と番号のついた \(M+1\) 個の箱が横一列に並んでいる。\(1,2,\dots,N\) と番号のついたボールをこれらの \(M+1\) 個の箱に分配する。このとき、箱 \(M\) は空でなく、また、少なくとも \(1\) つの箱は空であるようにする。その後、箱 \(M\) に入っているボールを空の箱のうち最も番号の小さいものに移す。

ボールの分配を決めることで移し替える操作は一意に定まるので、条件を満たす分配の方法を数え上げればよく、ボールの分配方法 \((M+1)^N\) 通りのうち、箱 \(M\) が空であるものが \(M^N\) 通り、すべての箱が空でないものが \((M+1)!S(N,M+1)\) 通りであるので、求める総和は以下のようになります。

\[(M+1)^N-M^N-(M+1)!S(N,M+1)\]

これは、スターリング数や階乗を前計算することでテストケースあたり \(O(\log N)\) で計算出来ます。前計算は \(O(N^2+M)\) で行うことが出来るので全体で \(O(N^2+M+T\log N)\) でこの問題を解くことが出来ました。

なお、最後の式は形式的冪級数を用いて導出することも出来ます(形式的冪級数による導出)。