Trung bình 1 đã giải Tỷ lệ chấp nhận 25.0%

Đếm Dãy Xúc Xắc

Đếm số dãy kết quả gieo xúc xắc có thứ tự với tổng cho trước.

Bạn sẽ học được gì

  • Xây đáp án từ các tổng nhỏ hơn
  • Viết công thức truy hồi theo lần gieo cuối
  • Lấy kết quả modulo một số nguyên tố lớn

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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].

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 973 ms - 5/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.