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