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.\)

vì \(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}\) và \(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}\) và \(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