Đế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
6
Note

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


  • 0
    161007thanhhiu    8:40 a.m. 3 Tháng 7, 2023

    bài này toàn các cao nhân IF ELSE


    • 8
      Vu_CG_Coder    6:38 p.m. 7 Tháng 10, 2021 chỉnh sửa 4

      ĐỀ :

      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\)


      • 0
        kienhc    4:29 p.m. 20 Tháng 7, 2021

        Oh my god đề của tui mô!!!!!=)))))


        • 0
          dang7rickroll    5:54 p.m. 17 Tháng 6, 2021

          Where is đề 🙂


          • 2
            ekhoavvdd    9:58 p.m. 23 Tháng 1, 2021

            thầy ơi mấy đề sao mà làm thầy :))

            2 phản hồi