Shuffle and Increasing を解きます。\(A\) を並び替えて得られる列の集合を \(S\) とします。ここで、\(\displaystyle f_k = \sum_{1 \le i_1 < i_2 < \dots < i_k \le N-1}^{} A_{i_j} < A_{i_{j+1}}\) を満たす \(A\) の個数と定義します。\(g_k\) を元の問題の \(M=k\) のときの答えと定義すると、\(f_k = \sum_{i=k}^{N-1} \binom{i}{k} g_i\) であるため \(f\) を求めると \(g\) を求めることが出来ます。

ここで \(i_1,i_2,\dots,i_k\) を固定すると、\(A\) を \(N-k\) 個のサイズの指定された狭義単調増加列に分割する問題を解くことになります。 さて、このように言い換えると \(B\) の度数分布が等しい場合 \(f_k\) が等しいことが分かります。よって、\(B\) を並び替えても答えが変わらないことが証明出来ました。