Đề bài
Một viên xúc xắc tiêu chuẩn cho ra một số nguyên từ 1 đến 6. Hãy đếm tất cả các dãy kết quả có thứ tự, không rỗng, sao cho tổng các số trong dãy bằng target. Các dãy có thứ tự khác nhau được tính riêng biệt. Trả về kết quả đếm theo modulo 1.000.000.007.
Cài đặt hàm dice_combinations(target).
Đầu vào
target: Tổng yêu cầu của tất cả các lần gieo.
Đầu ra
Trả về số lượng dãy theo modulo 1.000.000.007.
Ràng buộc
1 ≤ target ≤ 1.000.000. Việc lấy modulo 1.000.000.007 nghĩa là trả về phần dư của kết quả sau khi chia cho số này.
Ví dụ
Đầu vào:
target = 2
Kết quả mong đợi:
expected = 2Đầu vào:
long long target = 2;
Kết quả mong đợi:
long long expected = 2;Đầu vào:
long target = 2;
Kết quả mong đợi:
long expected = 2;Giải thích
Hai dãy là [2] và [1, 1].
Đầu vào:
target = 4
Kết quả mong đợi:
expected = 8Đầu vào:
long long target = 4;
Kết quả mong đợi:
long long expected = 8;Đầu vào:
long target = 4;
Kết quả mong đợi:
long expected = 8;Giải thích
Các dãy là [4], [1,3], [3,1], [2,2], [1,1,2], [1,2,1], [2,1,1] và [1,1,1,1].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Hãy xem các tổng nhỏ hơn như những viên gạch để xây tổng mục tiêu.
Gợi ý 2
Dùng một bộ đếm chạy cho mỗi tổng dựa trên 6 tổng trước đó.
Gợi ý 3
Nhớ áp dụng modulo ở mỗi phép cộng và xử lý riêng các tổng nhỏ hơn 1.
Độ phức tạp mong đợi
thời gian O(target), bộ nhớ phụ O(target)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.