Hướng dẫn cho Giấc mơ


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: jumptozero

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



Bình luận

Không có bình luận nào.