Tứ diện

Xem PDF




Thời gian:
Python 3 5.0s

Tác giả:
Dạng bài
Điểm: 450 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một tứ diện, đánh dấu các đỉnh lần lượt là \(A, B, C, D\).



Một con kiến ​​đang đứng trên đỉnh \(D\) của tứ diện. Con kiến ​​khá tích cực di chuyển và nó không chịu nhàn rỗi. Với mỗi bước đi, nó bước từ một đỉnh tới đỉnh khác dọc theo một số cạnh của tứ diện. Con kiến ​​không bao giờ chịu đứng yên ở một chỗ.

Yêu cầu: Đếm số cách mà con kiến ​​có thể đi từ đỉnh \(D\) ban đầu rồi quay về chính nó trong đúng \(n\) bước. Nói cách khác, bạn sẽ được yêu cầu tìm ra số con đường tuần hoàn khác nhau có chiều dài \(n\) từ đỉnh \(D\) đến chính nó. Vì số có thể khá lớn nên bạn nên in theo \(modulo (10^9 + 7)\).

Input

  • Dòng đầu tiên chứa số nguyên duy nhất \(n (1 \le n \le 10^7)\) - chiều dài của đường đi.

Output

  • In số nguyên duy nhất là kết quả tìm được \(modulo (10^9+ 7)\).

Scoring

  • Subtask \(1\) (\(25\%\) số điểm): \(n \le 10\)
  • Subtask \(2\) (\(25\%\) số điểm): \(n \le 10^7\)
  • Subtask \(3\) (\(50\%\) số điểm): \(n \le 10^{14}\)

Example

Test 1

Input
2
Output
3

Bình luận


  • 5
    hongquanyl1 9:59 p.m. 26 Tháng 10, 2021

    Anh jumptozero viết hương dẫn hay quá
    Ai thấy đúng cho xin cánh tay nào


    • 2
      jumptozero 10:11 a.m. 25 Tháng 2, 2021

      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


      • 0
        jumptozero 6:49 a.m. 25 Tháng 2, 2021 chỉnh sửa 4

        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


        • 0
          jumptozero 5:44 p.m. 24 Tháng 2, 2021

          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

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