最終的に袋に入るカードを1枚考えます。ある回の操作直前にこのカードが上から \(K\) 枚以内に来たならば、そのの操作で必ず袋に入れるとしてよいです。（袋に入れるのを先延ばしにすることによって、できる集合の選択肢が増えることはありません） よって、毎回の操作の前に上から \(K\) 枚以内にあるカードについては、それぞれの操作で袋に入れられるか二度と選ばれないかのどちらかになります。この考察により、操作を以下のように言い換えることができます。

• 上から \(K\) 枚のカードを見て、印のついていないカードを選び印を付ける。
• 上から \(K\) 枚のうち印のついていないカードを袋に入れる。

ここで、\(S_0=\{1,2, \cdots, K\}\) とすると、毎回の操作でのカードの選び方は\(S_0 \supseteq S_1 \supseteq \cdots \supseteq S_M\) を満たす集合の組 \((S_1, \cdots, S_M)\) と一対一対応します。（直感的には、\(S_i\) は \(i\) 回目の操作で印が付けられず残っているカードを表していると考えられます） したがって、可能な全ての組 \((S_1, \cdots, S_M)\) に対し \(\sum_{1 \leq i \leq M} |S_i|\) を求める問題に帰着されます。

各要素の寄与を考えます。整数 \(i \in S_0\) について、その寄与は \(i \in S_j\) を満たす最大の \(j\) と等しいです。また、寄与が \(j\) となるような通り数は \(i\) 以外の要素の寄与の通り数から \((M+1)^{K-1}\) です。これより、 \(i\) による寄与は \(j=0, \cdots, M\) と和をとることで \(\frac{M(M+1)}{2} (M+1)^{K-1}\) と求められます。 \(i=1,\cdots, K\) についてこれは成り立つので、 結論としてこの問題の答えは \(\frac{KM(M+1)^K}{2}\) となります。