Bình luận

• 
  

  6

  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

• 
  

  5

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

• 
  

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

• 
  

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

  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

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