Editorial for Tứ diện


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

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

Gọi \(A[n],B[n],C[n],D[n]\) lần lượt là số số con đường tuần hoàn khác nhau có chiều dài \(n\) từ đỉnh \(D\) đến các đỉnh \(A,B,C,D\).

Khi đó ta có: \(A[1]=1,B[1]=1,C[1]=1,D[1]=0\) và với \(n\ge 2\), ta có dãy truy hồi sau:

\(\left\{\begin{matrix} D[n]=A[n-1]+B[n-1]+C[n-1]\\ A[n]=B[n-1]+C[n-1]+D[n-1] \\ B[n]=A[n-1]+C[n-1]+D[n-1]\\ C[n]=A[n-1]+B[n-1]+D[n-1] \end{matrix}\right.\)

\(n\sim 10^7\) nên ta có thể hoàn toàn giải bài toán này trong \(O(n)\). Và để đỡ tốn bộ nhớ, chúng ta có thể giải quyết bài toán như sau:

$$$
ll n, fd, tmp_fd, fa, tmp_fa, fb, tmp_fb, fc, tmp_fc;
fd = 0, fa = fb = fc = 1;
cin >> n;

    for (ll i = 2; i <= n; i++)
    {

            tmp_fd = fd;
            fd = (fa + fb + fc) % mod;
            tmp_fa = fa;
            fa = (tmp_fd + fb + fc) % mod;
            tmp_fb = fb;
            fb = (tmp_fa + tmp_fd + fc) % mod;
            tmp_fc = fc;
            fc = (tmp_fa + tmp_fb + tmp_fd) % mod;
    }
    cout << fd;

$$$

Và khi đó \(fd\) chính là \(D[n]\) cần tìm.

Và đây là code của mình, các bạn có thể tham khảo tại đây: Link


Updated: Sau khi bộ test đã được update, thì có vẻ như thuật \(O(n)\) đã bị \(TLE\). Vì vậy, mình sẽ sử dụng nhân ma trận để giải quyết bài toán như sau:

$\left{\begin{matrix} D[n]=A[n-1]+B[n-1]+C[n-1]\ A[n]=B[n-1]+C[n-1]+D[n-1] \ B[n]=A[n-1]+C[n-1]+D[n-1]\ C[n]=A[n-1]+B[n-1]+D[n-1] \end{matrix}\right. $
\(\implies \begin{pmatrix}D[n] & A[n] & B[n] & C[n] \end{pmatrix}.\begin{pmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{pmatrix} = \begin{pmatrix}D[n+1] & A[n+1] & B[n+1] & C[n+1] \end{pmatrix}\)

Đặt \(p_n=\begin{pmatrix}D[n] & A[n] & B[n] & C[n] \end{pmatrix}\)\(M=\begin{pmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{pmatrix}\).

Khi đó ta có: \(p_{n+1}=p_n.M=...=p_1.M^{n-1}\) với \(p_1=\begin{pmatrix}0 & 1 & 1 & 1 \end{pmatrix}\)

Đến đây, sử dụng luỹ thừa nhị phân và nhân ma trận là xong.

Độ phức tạp : \(O(log(n))\)

Các bạn có thể tham khảo code tại đây: Link

Ps: Nếu có gì thắc mắc, các bạn cứ comment nhé !


Mình Bonus bài này một chút nữa như sau:

Gọi \(Q(n) = \frac{3.(9^{n-1}-1)}{4}\)\(G(n)=\frac{9^{n-1}-1}{4}\). Thì bằng quy nạp ta chứng minh được rằng:

\(M^n=\left\{\begin{matrix}M_1, \text{ với } n \text{ lẻ } \\ M_2, \text{ với } n \text{ chẵn } \end{matrix}\right.\)

Trong đó:

  • \(M_1=\begin{pmatrix} Q(k) & Q(k)+1 & Q(k)+1 & Q(k)+1\\Q(k)+1 & Q(k) & Q(k)+1 & Q(k)+1\\ Q(k)+1 & Q(k)+1 & Q(k) & Q(k)+1 \\ Q(k)+1 & Q(k)+1 & Q(k)+1 & Q(k) \end{pmatrix}\), với \(k=\frac{n+1}{2}\)

  • \(M_2=\begin{pmatrix} G(k)+1 & G(k) & G(k) & G(k)\\G(k) & G(k)+1 & G(k) & G(k)\\ G(k) & G(k) & G(k)+1 &G(k) \\ G(k) & G(k) & G(k) & G(k)+1 \end{pmatrix}\), với \(k=\frac{n+2}{2}\)

Do đó từ công thức: \(p_n=p_1*M^{n-1}\rightarrow (*)\)

  • TH1: Nếu \(n=2k,\text{ với }k\in \mathbb{N}^{*}\).

Khi đó \((*)\implies p_n = p_1*M^{n-1} =\begin{pmatrix} 0&1&1&1\end{pmatrix}.\begin{pmatrix} Q(k) & Q(k)+1 & Q(k)+1 & Q(k)+1\\Q(k)+1 & Q(k) & Q(k)+1 & Q(k)+1\\ Q(k)+1 & Q(k)+1 & Q(k) & Q(k)+1 \\ Q(k)+1 & Q(k)+1 & Q(k)+1 & Q(k)\end{pmatrix}\)

Hay \(\begin{pmatrix}D[n]&A[n]&B[n]&C[n]\end{pmatrix} =\begin{pmatrix} 0&1&1&1\end{pmatrix}.\begin{pmatrix} Q(k) & Q(k)+1 & Q(k)+1 & Q(k)+1\\Q(k)+1 & Q(k) & Q(k)+1 & Q(k)+1\\ Q(k)+1 & Q(k)+1 & Q(k) & Q(k)+1 \\ Q(k)+1 & Q(k)+1 & Q(k)+1 & Q(k)\end{pmatrix}\)
\(=\begin{pmatrix}3.Q(k)+3&3.Q(k)+2&3.Q(k)+2&3.Q(k)+2\end{pmatrix}\)

Từ đây ta suy ra được \(D[n]=3 * Q(k)+3\) với \(k=\frac{n}{2}\).

  • TH2: Tương tự, với \(n=2k+1\), ta tìm được \(D[n]=3 * G(k+1)\)

Và đến đây, sử dụng luỹ thừa nhị nhân, ta có thể giải quyết bài toán này trong \(O(log(n))\).

Và các bạn có thể tham khảo code tại đây: Link



Comments

There are no comments at the moment.