Đếm mảng (HSG10v1-2021)
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Hãy đếm xem có bao nhiêu mảng khác nhau \(a_1,a_2,...,a_n\) trong đó \(a_i\) nhận các giá trị nguyên dương trong đoạn \([1,M]\) sao cho tồn tại ít nhất một đoạn \(K\) giá trị liên tiếp giống nhau?.
Ở đây hai mảng được gọi là khác nhau nếu như tồn tại ít nhất một vị trí mà giá trị phần tử hai mảng ở vị trí này là khác nhau.
Input
- Một dòng duy nhất chứa ba số nguyên dương lần lượt là \(n, M, K\).
Output
- Ghi ra một số nguyên duy nhất là số lượng mảng khác nhau tìm được. Con số này có thể rất lớn nên bạn chỉ cần lấy phần dư của nó khi chia cho \(10^9+7\).
Constants
- \(1\leq n,M,K\leq10^6\).
Test 1
Input
3 2 2 Output
6Note
Các mảng tìm được là \((1, 1, 1)\), \((1, 1, 2)\), \((1, 2, 2)\), \((2, 1, 1)\), \((2, 2, 1)\), \((2, 2, 2)\).
Bình luận
ĐỀ :
Bài toán đơn giản:
Hãy đếm xem có bao nhiêu mảng khác nhau
a1,a2,...,an trong đó ai nhận các giá trị nguyên dương trong đoạn [1,M] sao cho tồn tại ít nhất một đoạn K giá trị liên tiếp giống nhau?.
Ở đây hai mảng được gọi là khác nhau nếu như tồn tại ít nhất một vị trí mà giá trị phần tử hai mảng ở vị trí này là khác nhau.
Dữ liệu: một dòng duy nhất chứa ba số nguyên dương lần lượt là n M K.
Kết quả:Ghi ra một số nguyên duy nhất là số lượng mảng khác nhau tìm được. Con số này có thể rất lớn nên bạn chỉ cần lấy phần dư của nó khi chia cho 1e9+7
INPUT : 3 2 2
OUTPUT : 6
Giải thích: Các mảng tìm được là (1, 1, 1), (1, 1, 2), (1, 2, 2), (2, 1, 1), (2, 2, 1), (2, 2, 2)
Giới Hạn : 1<=n,M,K<=\(10^6\)
4 bình luận nữa