Đầu tiên, chúng ta cần nhận thấy tích của các lần gieo xúc xắc chỉ có thể có dạng \(2^a * 3^b * 5^c\). Đồng thời, chúng ta có thể phân tích \(m\) theo dạng này trong \(O(\log m)\). Nếu \(m\) có ước nguyên tố khác \(2, 3, 5\) thì đáp số là \(0\).

Đến đây chúng ta có \(2\) cách.

Cách 1: Quy Hoạch Động

Chúng ta sẽ lưu trạng thái là: số lần gieo và phân tích thừa số nguyên tố của số hiện tại. \(dp[n][x][y][z]\) là số cách gieo xúc xắc \(n\) lần sao cho tích của chúng là \(2^x3^y5^z\). Mỗi bước chuyển trạng thái từ \(n\) sang \(n + 1\), chúng ta sẽ có \(6\) cách chuyển tương ứng với \(6\) cách gieo \(1, 2, 3, 4, 5, 6\).

Đáp số là \(dp[n][a][b][c]\)

Độ phức tạp: \(O(n * \log^3 m)\)

Cách 2: Tổ hợp

Gọi \(x_1, x_2, ..., x_6\) là số lần gieo trúng \(1, 2, ..., 6\). Khi đó chúng ta có các đẳng thức sau:

\(\left\{\begin{matrix} x_2+2x_4+x_6=a\\ x_3+x_6=b\\ x_5=c\\ x_1+x_2+x_3+x_4+x_5+x_6=n \end{matrix}\right.\)

Từ đó thấy rằng, nếu chúng ta xác định trước được \(x_4\) và \(x_6\), tất cả những số \(x_i\) sẽ được xác định. Đồng thời với mỗi bộ số \((x_1, x_2, ..., x_6)\), số cách gieo sẽ là \(\dfrac{n!}{x_1!x_2!...x_6!}\).

Như vậy, chúng ta cần hai vòng for cho \(x_4\) và \(x_6\) rồi tổng hết tất cả cách gieo. Dễ thấy rằng, mỗi vòng for này không cần chạy quá \(O(\log m)\). Nên độ phức tạp là \(O(\log^2 m)\).