Giấc mơ

Xem PDF




Tác giả:
Dạng bài
Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Sau một ngày mệt nhọc đón các đoàn về tham dự Trại hè tin học 2017, thầy Minh vô cùng mệt mỏi ngủ ngay khi học sinh về hết phòng. Trong giấc mơ, thầy Minh mơ đang vẽ một cây vô hạn, mỗi nút có đúng \(n\) nút con, khoảng cách từ nút cha tới các nút con của nó theo thứ tự từ trái sang phải là \(d_1, d_2, … , d_n\). Thầy Minh đang có một số \(k\) và rất muốn biết có bao nhiêu đỉnh trên cây mà khoảng cách từ đỉnh đó tới gốc không vượt quá \(k\).

Dữ liệu

  • Dòng đầu chứa hai số nguyên dương \(n\)\(k\).
  • Dòng thứ hai chứa \(n\) số nguyên dương \(d_1, d_2, … , d_n (d_i ≤ 100)\)

Kết quả

  • Số lượng đỉnh mà khoảng cách từ đỉnh đó tới gốc không vượt quá \(k\). Đưa ra theo số dư cho \(10^9 + 7\).

Input

3 3 
1 2 3

Output

8

Giới hạn

  • 50% test có \(k ≤ 10000, n ≤ 100\)
  • 50% test có \(1000 < k ≤ 10^{18}, n≤ 100000\)

Nguồn: CĐ DHBB


Bình luận


  • 2
    T2K30 10:23 p.m. 15 Tháng 11, 2021 đã chỉnh sửa

    • 2
      jumptozero 10:12 a.m. 2 Tháng 3, 2021

      Mình xin chia sẻ lời giải bài này như sau:

      Gọi \(F[t]\) là số đỉnh mà đường đi từ nó đến gốc có tổng là \(t\). Khi đó ta có: \(F[t]=\sum \limits_{i=1}^{n}F[t-d_i]\)

      gọi \(G[k]\) là số đỉnh mà đường đi từ nó đến gốc có tổng nhỏ hơn hoặc bằng \(k\). Khi đó ta có: \(G[k]=G[k-1]+F[k]\)

      Khi đó ta có công thức truy hồi sau:

      \(\left\{\begin{matrix}G[k]=G[k-1]+F[k] \\ F[k]=f[1]*F[k-1]+f[2]*F[k-2]...+f[100]*F[k-100]\end{matrix}\right.\)

      Trong đó \(f[i](\forall 1\le i\le 100)\) chính là tần số của số \(i\) trong mảng \(d_i(\forall 1\le i\le n)\) đã cho.

      Từ đây, ta suy được công thức truy hồi theo ma trận như sau:

      \(\begin{pmatrix}G[k-2]&F[k-1]&...&F[k-100]\end{pmatrix}.\begin{pmatrix} 1&0&0&...&0 \\1 & f[1] & 1&...&0\\ ... \\ 0 & f_{100} & 0 & ... & 0\end{pmatrix} = \begin{pmatrix}G[k-1]&F[k]&...&F[k-99]\end{pmatrix}\)

      Đến đây đặt \(p_k = \begin{pmatrix}G[k-1]&F[k]&...&F[k-99]\end{pmatrix}\)\(M=\begin{pmatrix} 1&0&0&...&0 \\1 & f[1] & 1&...&0\\ ... \\ 0 & f[100] & 0 & ... & 0\end{pmatrix}\). Ta suy ra được:

      \(p_k = p_{k-1}.M=p_0.M^{k}\)

      Đến đây sử dụng luỹ thừa nhị phân, ta đã giải quyết xong bài toán.

      Ps: Ở đây, mình giải thích một chút về công thức truy hồi như sau:

      Vì đề bài cho \(d_i\le 100\) nên ta có: \(F[t]=\sum \limits_{i=1}^{n}F[t-d_i] = f[1]*F[t-1]+f[2]*F[t-2]...+f[100]*F[t-100]\).

      Ps2: Để hiểu được vì sao có được ma trận \(M\) đó, các bạn viết tay ra là sẽ thấy nhé

      Ps3: Nếu có gì thắc mắc, các bạn cứ comment nhé , các bạn có thể tham khảo code tại đây