~m = 1~.

• Dễ thấy ~a_i = b_i~, nên đáp án là ~k^x~ với ~x~ là số giá trị ~b_i~ bằng ~-1~.

• Độ phức tạp ~\mathcal{O}(n)~.

~n \le 20~, ~k = 2~.

• Với subtask này, ta sẽ duyệt qua ~2^n~ cách điền dãy ~a~ và kiểm tra mỗi dãy ~a~ có thỏa mãn không.

• Độ phức tạp ~\mathcal{O}(n2^n)~.

~m = 2~.

• Với ~m = 2~, mỗi giá trị ~a_i~ chỉ có ảnh hưởng đến tối đa ~2~ giá trị ~b_{i - 1}~, ~b_i~ (nếu có), nên ta có thể quy hoạch động.

• Gọi ~dp(i, t)~ là số cách điền các giá trị cho ~i~ phần tử đầu của dãy ~a~, và ~t~ là ~a_i~ có bằng ~b_i~ không. Đặt ~v = \min(b_i, b_{i + 1})~, dễ thấy ~a_{i + 1} \le v~, ta có các trường hợp:

  • Với ~dp(i, 0)~, vì ~a_i < b_i~ nên phải điền ~a_{i + 1} = b_i~ để thỏa mãn ~b_i = \max(a_i, a_{i + 1})~. Nếu ~b_i > v~, ta không thể điền ~a_{i + 1} = b_i~, còn nếu ~b_i = v~ thì ~dp(i + 1, t) \leftarrow dp(i, 0)~ (với ~t~ bằng ~1~ nếu ~v = b_{i + 1}~, còn lại bằng ~0~, theo đúng định nghĩa hàm ~dp~).

  • Với ~dp(i, 1)~, xét trường hợp điền ~a_{i + 1} < b_{i + 1}~, ta sẽ có ~a_{i + 1} \le \min(b_{i + 1} - 1, v)~, vì vậy ~dp(i + 1, 0) \leftarrow dp(i, 1) \cdot \min(b_{i + 1} - 1, v)~; còn trường hợp ~a_{i + 1} = b_{i + 1}~, ta chỉ điền được nếu ~b_{i + 1} = v~, khi đó ~dp(i + 1, 1) \leftarrow dp(i, 1)~.

• Lưu ý cần xử lý các trường hợp ~b_i = -1~, khi đó ta coi ~b_i = k~, và coi mọi cách điền ~a_i~ đều thỏa mãn ~a_i = b_i~, tức là mọi trạng thái đều chuyển đến ~dp(i, 1)~ chứ không phải ~dp(i, 0)~.

• Độ phức tạp ~\mathcal{O}(n)~.

~m \le 8~.

• Tương tự subtask ~3~, nhưng thay vì lưu một chiều ~t~ thì ta lưu ~m - 1~ chiều (biểu diễn bằng bitmask), sau đó chuyển trạng thái bằng cách xét giá trị nhỏ nhất tương tự như trên.

• Độ phức tạp ~\mathcal{O}(n2^{m - 1})~.

~k = 2~.

• Dễ thấy nếu ~b_i = 1~ thì ~a_j = 1~ với ~i \le j \le i + m - 1~. Sau khi cố định được các ~a_j = 1~, ta chỉ cần quan tâm các giá trị ~b_i = 2~. Ta có ~dp(i)~ là số cách điền ~i~ phần tử đầu sao cho ~a_i = 2~. Nếu ta đã cố định được ~a_i = 1~ từ trước thì ~dp(i) = 0~.

• Gọi ~p~ là vị trí nhỏ nhất lớn hơn ~i~ thỏa mãn ~b_p = 2~, khi đó ta bắt buộc phải đặt một phần tử bằng ~2~ trước vị trí ~p + m~. Vì vậy ~dp(j) \leftarrow dp(i)~ với ~i < j < p + m~.

• Gọi ~q~ là vị trí cuối cùng mà ~b_q = 2~, đáp án là tổng các ~dp(i)~ với ~q \le i~.

• Ta có thể tối ưu phần chuyển trạng thái bằng tổng tiền tố.

• Độ phức tạp ~\mathcal{O}(n)~.

~b_i \ne -1\ \forall\ 1 \le i \le n - m + 1~.

• Nếu ~b_i > b_{i + 1}~, do ~a_j \le b_{i + 1}~ (~i < j \le i + m - 1~), nên để ~\displaystyle b_i = \max_{i \le j \le i + m - 1} a_j~ thì ~a_i = b_i~.

• Tương tự, nếu ~b_i < b_{i + 1}~, ta cũng dễ dàng chứng minh được ~a_{i + m} = b_{i + 1}~.

• Ta chia ra các đoạn liên tiếp có ~b_i~ bằng nhau, giả sử đang xét đoạn bằng nhau ~[x, y]~, ta xác định được hai biên ~l~, ~r~ tương ứng trên dãy ~a~.

  • Với ~r~, nếu ~b_y > b_{y + 1}~ thì ~r = y~, ngược lại nếu ~b_y < b_{y + 1}~ thì ~r = y + m - 1~.

  • Tương tự ta cũng xác định được biên ~l~.

  • Trong trường hợp ~l > r~, ta không thể điền các giá trị thỏa mãn nên đáp án sẽ là ~0~.

  • Còn nếu ~l \le r~, ta xét các giá trị ~a_i~ chưa được cố định trong ~[l, r]~ (lưu ý có thể có giá trị ~a_i = b_x~ đã được cố định ở biên ~l~ hoặc ~r~, ta bỏ qua các giá trị này), cần điền giá trị cho các ~a_i~ đó sao cho giá trị lớn nhất của ~m~ phần tử liên tiếp bất kì của đoạn đó đều bằng ~b_x~.

  • Ta có thể quy hoạch động gần như subtask ~5~, gọi ~l'~, ~r'~ lần lượt là biên trái, phải của dãy giá trị ~a_i~ chưa cố định ở trên, sau đó ta có ~dp(i)~ là số cách điền ~i~ phần tử đầu trong đoạn ~[l', r']~ thỏa mãn giá trị lớn nhất của ~m~ phần tử liên tiếp đều bằng ~b_x~, sau đó ta chuyển trạng thái ~dp(j) \leftarrow dp(i) + (b_x - 1)^{j - i - 1}~ với ~i < j \le i + m~.

  • Có thể tối ưu công thức quy hoạch động bằng cách tách riêng phần lũy thừa: $$\displaystyle dp(j) = \sum_{j - m \le i < j} dp(i) \cdot (b_x - 1)^{j - i - 1}$$ $$\displaystyle \Leftrightarrow dp(j) = (b_x - 1)^j \cdot \sum_{j - m \le i \le j} \dfrac{dp(i)}{(b_x - 1)^{i + 1}}$$

  • Vì ~\displaystyle \sum_{j - m \le i \le j} \dfrac{dp(i)}{(b_x - 1)^{i + 1}}~ phụ thuộc hoàn toàn vào ~i~ nên ta có thể sử dụng tổng tiền tố để tính nhanh.

• Độ phức tạp ~\mathcal{O}(n \log_2 1\ 000\ 000\ 005)~ do ta cần tính nghịch đảo modulo.

~n \le 2000~.

• Đặt ~\displaystyle c_i = \min_{i - m + 1 \le j \le i} b_j~, thì ta có điều kiện cần là ~a_i \le c_i~. Nhận thấy nếu bài toán chỉ là đếm số dãy thỏa mãn ~\displaystyle \max_{i \le j \le i + m - 1} a_j \le b_i~ ~(*)~ thì việc tính toán sẽ rất dễ dàng (đáp án là ~\displaystyle \prod_{i = 1}^{n} c_i~), vì vậy ta sẽ sử dụng nguyên lí bao hàm loại trừ để chuyển bài toán gốc thành bài toán trên.

• Ta đếm số dãy thỏa mãn điều kiện ~(*)~ nhưng không thỏa mãn đề bài, tức tồn tại ít nhất một vị trí ~i~ mà ~\displaystyle \max_{i \le j \le i + m - 1} a_j \le b_i - 1~. Gọi ~S_i~ là tập các dãy ~a~ thỏa mãn điều kiện ~(*)~ và ~\displaystyle \max_{i \le j \le i + m - 1} a_j \le b_i - 1~. Khi đó số dãy ~a~ thỏa mãn đề bài là ~\displaystyle \prod_{i = 1}^{n} c_i - \left\lvert\bigcup_{i = 1}^n S_i\right\rvert~.

• Với mọi ~P~ là một tập con của tập các số nguyên từ ~1~ đến ~n~, ta cần tính ~\displaystyle \left\lvert\bigcup_{i \in P} S_i\right\rvert~. Ta có dãy ~f~ được định nghĩa như sau: nếu ~b_i \in P~ thì ~f_i = b_i - 1~, ngược lại ~f_i = b_i~, sau đó ta tạo dãy ~g~ dựa trên dãy ~f~ tương tự như dãy ~c~, với ~\displaystyle g_i = \min_{i - m + 1 \le j \le i} f_j~. Khi đó ~\displaystyle \left\lvert\bigcup_{i \in P} S_i\right\rvert = \prod_{i = 1}^n g_i~.

• Nhận thấy ~g_i = c_i - 1~ khi và chỉ khi tồn tại một chỉ số ~j~ sao cho ~i - m + 1 \le j \le i~, ~b_j = c_i~ và ~j \in P~, nếu không tồn tại ~j~ thỏa mãn thì ~g_i = c_i~. Do đó có thể xử lí riêng các giá trị ~b_j~ và ~c_i~ bằng nhau một cách độc lập với các các ~b_j~, ~c_i~ có giá trị khác. Với mỗi giá trị ~x~ từ ~1~ đến ~k~, gọi ~pb_x~ là tập các vị trí ~i~ sao cho ~b_i = x~, ~pc_x~ là tập các vị trí ~i~ sao cho ~c_i = x~. Vì ta cần quan tâm đến tính chẵn lẻ của ~|P|~, nên ta có ~dp(i, t)~ là số cách chọn của ~i~ vị trí đầu trong tập ~pb_x~ sao cho ~pb_x(i) \in P~, và ~t~ là tính chẵn lẻ của số lượng phần tử đã chọn. Ta có thể dễ dàng chuyển trạng thái như sau:

  • Gọi ~l_i, r_i~ là khoảng tương ứng trên ~pc_x~ mà ~pb_x(i)~ phủ, hay ~l_i~ là vị trí ~j~ đầu tiên sao cho ~pc_x(j) \ge pb_x(i)~, ~r_i~ là vị trí ~j~ cuối cùng sao cho ~pc_x(j) < pb_x(i) + m~. Khi xét đến ~dp(i, t)~ thì ta đã phải điền hết giá trị ~g~ đến ~r_i~.

  • Đang ở trạng thái ~i~, ta chọn phần tử ~j~ tiếp theo vào tập ~P~, xét trường hợp tập giá trị được phủ của ~i~ và ~j~ không giao nhau hay ~r_i < l_j~, ta thấy các giá trị ~g~ trong đoạn ~(r_i, l_j)~ chỉ cần không vượt quá ~x~, còn các giá trị ~g~ trong khoảng ~[l_j, r_j]~ phải có giá trị không vượt quá ~x - 1~, nên ~dp(j, t) \leftarrow dp(i, 1 - t) \cdot x^{l_j - r_i - 1} \cdot (x - 1)^{r_j - l_j + 1}~.

  • Nếu hai tập giá trị giao nhau hay ~r_i \ge l_j~, thì các giá trị ~g~ trong ~(r_i, r_j]~ sẽ có giá trị không quá ~x - 1~, ta có ~dp(j, t) = dp(i, 1 - t) \cdot (x - 1)^{r_j - r_i}~.

• Sau khi tính được đáp án với ~\forall \ x~, ta dễ dàng kết hợp lại để tính được kết quả cuối cùng.

• Độ phức tạp ~\mathcal{O}(n^2)~.

không có ràng buộc gì thêm.

• Tối ưu công thức quy hoạch động của subtask ~7~ tương tự như subtask ~6~.

• Độ phức tạp ~\mathcal{O}(n + k \log_2 1\ 000\ 000\ 005)~ do ta cần tính nghịch đảo modulo.