\(M, D\) ともに各桁の合計が \(k\) となる組み合わせの数 \(C_M(k), C_D(k)\) を計算する. 答えは \(\sum C_M(k)C_D(k)\) となる.

組み合わせの数を求めるには桁 DP を使う.

\(i\) 桁目まで見た, 各桁の合計が \(j\) である, 最大値かどうか \(k\) をキーにして組み合わせの数を \(C(i, j, k)\) を考えて, これを DP で更新していけば組み合わせの数を求めることができる.