Giấc mơ
Xem PDF
Đ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\) và \(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
sauce: https://codeforces.com/contest/514/problem/E
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}\) và \(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