Subtask 1

Ta gọi \(F(i, j)\) là số cách đi đến ô \((i, j)\) từ ô \((2,1)\).
Với subtask này, ta chỉ cần dùng quy hoạch động tính tất cả \(F(i,j)\) trong bảng \(3 \times m\).
Kết quả là \(F(2,m)\).

Độ phức tạp: \(O(3 \cdot m)\)

Subtask 2

Tương tự subtask 1. Tuy nhiên trong subtask này, ta cần xác định các ô có là chướng ngại vật hay không, những ô là chướng ngại vật ta sẽ mặc định ô đó \(F(i, j) = 0\).
Vì các chướng có thể chồng lên nhau nên để xác định được từng ô có chướng ngại vật không thì ta có thể dùng tăng đầu giảm cuối để tính.

Độ phức tạp: \(O(3 \cdot m)\)

Subtask 3

Nhận xét: Nếu không có chướng ngại vật nào trong cột thứ \(i\) và ta đã tính được số cách để đi đến các ô trong cột \(i-1\) thì số cách đi đến các ô trong cột \(i\) được tính bằng cách nhân ma trận như sau:

Vì ở subtask này \(n = 0\) nên không có chướng ngại vật nào trên đường, kết quả sẽ là:

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

Subtask 4

Ta thấy các chướng ngại vật đã được sắp xếp tăng dần và không có cột nào chứa nhiều hơn \(1\) chướng ngại vật. Với mỗi chướng ngại vật, ta sẽ tính số cách đi đến cột \(l_i - 1\) và từ đó ta sẽ tính số cách đi đến cột \(r_i\):

• Tính số cách đi đến cột \(l_i - 1\):
  \(\begin{bmatrix} F(1,l_i - 1) & F(2,l_i - 1) & F(3,l_i - 1) \end{bmatrix} = \begin{bmatrix} F(1, r_{i - 1}) & F(2, r_{i-1}) & F(3, r_{i-1}) \end{bmatrix} \begin{bmatrix} 1 & 1 & 0\\ 1 & 1 & 1\\ 0 & 1 & 1 \end{bmatrix} ^ {l_i - 1 - r_{i-1}}\)
  (Lưu ý trường hợp \(i = 1\)).
• Tính số cách đi đến cột \(r_i\):
• Trường hợp 1: \(a_i = 1\):
• \(F(1, r_i) = 0\)
• Nếu: \(l_i = r_i\) thì:
  • \(F(2, r_i) = F(1,l_i - 1) + F(2, l_i - 1) + F(3, l_i - 1)\)
  • \(F(3, r_i) = F(2, l_i - 1) + F(3, l_i - 1)\)
• Nếu: \(l_i < r_i\) thì:
  • \(F(2, r_i) = F(3, r_i) = (F(1, l_i - 1) + F(2, l_i - 1) \cdot 2 + F(3, l_i - 1) \cdot 2) \cdot 2^{r_i - l_i}\)
• Trường hợp 2: \(a_i = 2\):
• \(F(1, r_i) = F(1, l_i - 1) + F(2, l_i - 1)\)
• \(F(2, r_i) = 0\)
• \(F(3, r_i) = F(2, l_i - 1) + F(3, l_i - 1)\)
• Trường hợp 3: \(a_i = 3\): áp dụng, tính tương tự như trường hợp 1.

Sau khi tính được số cách đi đến các ô ở cột \(r_n\), ta sẽ tính số cách đi đến các ô ở cột \(m\) tương tự như subtask 3.

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

Subtask 5

Chúng ta sẽ chia đường thành \(2 \cdot n + 1\) đoạn, sao cho các điểm đầu mút của mỗi đoạn là các \(l_i\) - 1, \(r_i\), \(1\) và \(m\).

Với mỗi đoạn, những hàng nào chứa toàn chướng ngại vật thì giá trị trong ma trận nhân của cột tương ứng sẽ trở thành \(0\).

Gọi \((l, r)\) là 2 điểm đầu mút của đoạn, A là ma trận \(3 \times 3\) ở trên. Ta tính số cách đi đến cột \(r\) như sau:

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