題意の条件を満たす整数列の個数を明示的に求めます.

整数列 \(\{A_i\}\) に対して, 整数列 \(\{B_i\}\) を \(B_i := A_i-10(N-i)\) で定めます. このとき, \(\{A_i\}\) が題意の条件を満たすことと, \(\{B_i\}\) が以下の条件を満たすことが同値であることが確認できます.

• \(\{B_i\}\) は広義単調増大, \(\> i.e. \> B_1 ≤ \dots ≤ B_N\)
• \(1 ≤ B_1 , \> B_N ≤ M-10N+10 \)

上の条件を満たす整数列 \(\{B_i\}\) の個数は, \(1\) 以上 \((M-10N+10)\) 以下の整数を重複も込めて \(N\) 個選ぶ場合の数に一致するので, \(\left( \begin{array}{cc} M-9N+9 \\ N \end{array} \right) \) 個となります. \(\> \{A_i\}\) と \(\{B_i\}\) は1:1対応しているので, 題意の条件を満たす整数列の個数も同じ値となります.

公式解説の通りですが, 本問題の制約における最大ケースは \(N=12, \> M = 120\) のときで, 題意の条件を満たす整数列の個数は\(\left( \begin{array}{cc} 21 \\ 12 \end{array} \right) = 293930\) 個となります.