Subtask ~1~: ~n\le 7~

Với giới hạn ~n~ rất bé, ta chỉ cần backtrack duyệt hết hoán vị có thể tạo từ dãy ~a'~ và kiểm tra xem ~a~ có phải hoán vị ~k~-good với mọi ~k~ từ ~0~ đến ~n-1~ hay không. Một trong những phương án kiểm tra là sử dụng một std::map để kiểm tra xem có tồn tại một hoán vị nào khác có ma trận MEX giống hệt thỏa mãn không.

Tuy nhiên, vì không có giới hạn tổng ~n~ hay ~t~ cho subtask này, số lượng test case trong một test có thể rất lớn, việc duyệt và kiểm tra lại từ đầu với từng test case sẽ rất dễ dẫn đến kết quả TLE (Time Limit Exceed).

Để cải tiến, ta nên sinh trước tất cả hoán vị ~k~-good độ dài ~n~ với mọi ~0\le k<n\le 7~. Như vậy mỗi khi backtrack sinh dãy cho một test case, ta có thể bỏ qua khâu kiểm tra và cộng kết quả ngay lâp tức, đồng thời cách cài đặt này giúp việc kiểm tra dễ dàng hơn rất nhiều.</p>

Subtask ~2~: Trong tất cả test case, ~a'_i=-1~ với mọi ~i~ từ ~1~ đến ~n~

Từ subtask này, ta sẽ cần có một số nhận xét để xác định tính thỏa mãn của một hoán vị ~k~-good.

Với một hoán vị ~a~, định nghĩa ~f_a(i)~ (~0\le i<n~) là đoạn con ~[l;r]~ <strong>có độ dài nhỏ nhất chứa tất cả các số từ ~0~ đến ~i~, và ~|f_a(i)|=r-l+1~ là độ dài của đoạn con đó. Có thể nhận thấy từ dãy ~f_a~, ta dễ dàng dựng lại được ma trận MEX của hoán vị ~a~:

• ~M_{i,j}~ (~i\le j~) sẽ bằng số giá trị ~x~ sao cho ~f_a(x)~ nằm hoàn toàn trong đoạn ~[i;j]~.

Nhận xét 1: Nếu ~f_a=f_b~ thì hai hoán vị ~a~ và ~b~ có ma trận MEX giống nhau và ngược lại, nếu ~f_a\ne f_b~ thì hai hoán vị có ma trận MEX khác nhau.

Từ cách dựng đã nhắc đến ở trên, ta dễ dàng suy ra nhận xét này.

Nhận xét 2: Mọi hoán vị ~a~ đều là hoán vị ~0~-good ~(1)~.

Chứng minh: Nếu tồn tại một hoán vị ~b~ thỏa mãn thì ~f_a(0)\ne f_b(0)~, vì thế nên ~f_a\ne f_b~. Từ nhận xét 1, dễ dàng nhận thấy điều này vô lý do hai ma trận MEX chắc chắn khác nhau.

——————————————————————-

Từ các nhận xét sau, ta sẽ chứng minh theo cách "điền số". Rõ ràng ~a~ là hoán vị ~k~-good khi và chỉ khi: Từ dãy ~f_a~ cho trước, chỉ suy ra được một vị trí để "đặt" giá trị ~k~ vào hoán vị.

Nhận xét 3: Nếu ~f_a(k)\ne f_a(k-1)~ thì ~a~ là hoán vị ~k~-good ~(2)~.

Chứng minh: Trong trường hợp này, chỉ có một cách để "đặt" giá trị ~k~ là đặt vào đầu mút của ~f_a(k)~ thỏa mãn không nằm trong đoạn con ~f_a(k-1)~. Cách đặt duy nhất này sẽ đảm bảo đoạn ~f_a(k-1)~ được "mở rộng" ra chính xác đoạn ~f_a(k)~ mong muốn.

Một cách biểu diễn khác cho nhận xét này là: Nếu ~k~ nằm bên trái hoặc bên phải so với tất cả số từ ~0~ đến ~k-1~ thì ~a~ là hoán vị ~k~-good.

Nhận xét 4: Nếu ~f_a(k)=f_a(k-1)~ và ~|f_a(k)|\ne k+1~ thì ~a~ không phải là hoán vị ~k~-good.

Chứng minh: Đoạn ~f_a(k)~ không được mở rộng ra nên ta chỉ có thể "đặt" ~k~ vào trong đoạn ~f_a(k-1)~. Trong trường hợp này, luôn có ít nhất hai vị trí có thể "đặt" ~k~ vào. Vì thế nên ~a~ không phải là hoán vị ~k~-good.

——————————————————————-

Từ nhận xét 4, ta cũng suy ra được nếu ~|f_a(k)|=k+1~ thì chỉ có duy nhất một vị trí đặt ~k~ thỏa mãn, nhưng để vị trí này cố định thì cần phụ thuộc thêm vào vị trí của các số trước đó nữa (bao gồm các số từ ~0~ đến ~k-1~).

Ta sẽ xét trường hợp ~f_a(k)=f_a(k-1)~ và ~|f_a(k)|=k+1~. Gọi ~t~ (~t<k-1~) là vị trí lớn nhất thỏa mãn ~|f_a(t)|=t+1~. Ta không thể biết chính xác vị trí của các số từ ~0~ đến ~t~, tuy nhiên ta biết được tất cả số đó đều nằm trong một đoạn cố định, và đoạn này không chứa bất kỳ số nào khác.</p>

Ta bắt đầu xét các số từ ~t+1~ đến ~k~:

• Xét ~t+1~, rõ ràng ~f_a(t+1)\ne f_a(t)~ do trong đoạn ~f_a(t)~ không còn vị trí để điền số nữa. Nhưng nếu ~|f_a(t+1)|=t+2~ thì giá trị ~t~ không còn thỏa mãn như định nghĩa đã nêu ở trên nữa, vô lý.

• Nếu ~|f_a(t+1)|>t+3~ thì từ các số sau sẽ tồn tại một số có ít nhất hai cách "điền", vì thế nên vị trí của ~k~ không còn đảm bảo được cố định nữa. Vì thế nên ~|f_a(t+1)|=t+3~.

• Lập luận tương tự, ta cũng suy ra được ~|f_a(t+2)|=t+4,|f_a(t+3)|=t+5,\dots~. Ta có thể viết lại như sau: Với mọi ~i~ từ ~t+1~ đến ~k-1~, ~|f_a(i)|=i+2~.

• Với số ~k~, chỉ có duy nhất một cách điền, các số ~i~ từ ~t+1~ đến ~k-1~ có thể xác định chính xác vị trí do ~f_a(i)\ne f_a(i-1)~ ~(2)~, vì thế nên vị trí của ~k~ sẽ đảm bảo cố định.

Từ chứng minh trên, ta có thêm một nhận xét để kiểm tra tính thỏa mãn của hoán vị ~k~-good:

Nhận xét 5: Nếu ~f_a(k)=f_a(k-1),|f_a(k)|=k+1~ và với mọi ~i~ từ ~t+1~ đến ~k-1~, ~|f_a(i)|=i+2~ thì ~a~ là hoán vị ~k~-good (với ~t~ đã được định nghĩa như trên) ~(3)~.

Ta cũng có thể biểu diễn cách "điền" mô phỏng cho nhận xét này theo cách như sau (*):

• Ta "cố định" trước vị trí của ~k~, rõ ràng vị trí này phải nằm cạnh một trong hai đầu mút của ~f_a(t)~.

• Sau đó, điền các số từ ~t+1~ đến ~k-1~ theo hướng "mở rộng đoạn", mỗi số chọn một trong hai cách mở rộng đầu mút.

——————————————————————-

Bắt đầu đến phần tính toán, có ba trường hợp cần xét tương ứng. Gọi ~ans_i~ là đáp án cho ~k=i~:

• ~(1)~: ~ans_0=n!~ do không có số nào được điền ban đầu, vì thế nên tất cả hoán vị độ dài ~n~ đều có thể xét. Mở rộng: Nếu đã có ~m~ số được điền trước thì ~ans_0=(n-m)!~.

• ~(2)~: Có hai trường hợp cần xét: ~k~ nằm ở bên trái hoặc bên phải. Do chưa có số nào được điền, số cách thay vào đó sẽ được gấp đôi lên. Số cách thỏa mãn cho trường hợp ~(2)~ sẽ bằng:

  $$2\times k!\times C(k+1,n)\times (n-k-1)!$$ $$=\frac{n!\times 2\times k!\times (n-k-1)!}{(k+1)!(n-k-1)!}$$ $$=\frac{2\times n!}{k+1}$$

• ~(3)~: Giả sử ta cố định trước giá trị ~t~ (~t<k-1~), khi đó các số từ ~t+1~ đến ~k-1~ <strong>luôn có chính xác hai cách điền. Số cách thỏa mãn cho trường hợp ~(3)~ sẽ bằng:

  $$(n-k)\times (n-k-1)!\times \left(\sum^{k-2}_{t=0} t!\times 2^{k-t-1}\right)$$ $$(n-k)!\times \left(\sum^{k-2}_{t=0} t!\times 2^{k-t-1}\right)$$

Từ các công thức trên, ta có thể xác định các giá trị ~ans_0,ans_1,\dots,ans_{n-1}~ với độ phức tạp ~O(n^2)~.

Bonus: Ta có thể cải tiến công thức ~(3)~ do phần tính ~\sum^{k-2}_{t=0} t!\times 2^{k-t-1}~ có thể xử lý bằng công thức truy hồi, vì thế nên độ phức tạp sẽ giảm xuống còn ~O(n)~. Phần công thức truy hồi xin nhường lại bạn đọc.

Độ phức tạp: ~O(n^2)~ hoặc ~O(n)~ cho mỗi test case.

Subtask ~3~: Tổng ~n~ qua tất cả test case không vượt quá ~500~

~(2)~: Xét một giá trị ~k~ cụ thể, giả sử cố định trước vị trí của ~k~, ta xét hai trường hợp: ~k~ ở bên trái hoặc phải so với các số nhỏ hơn. Để đếm số cách thỏa mãn điều kiện, ta vẫn có thể giải quyết bằng tổ hợp:

• Giả sử không tồn tại số ở bên trái ~k~, tức là có thể xét đến trường hợp tất cả số nhỏ hơn ~k~ nằm bên phải. Gọi ~pos~ là vị trí của ~k~, ~cntright~ là số lượng vị trí bên phải ~pos~ chưa được điền, ~cntmiss~ là số lượng vị trí chưa được điền không bao gồm ~pos~, ~pcnt~ là số lượng số nhỏ hơn ~k~ chưa xuất hiện trong dãy. Khi đó số cách sẽ bằng:

  $$\frac{cntright!}{(cntright-pcnt)!}\times (cntmiss-pcnt)!$$

• Lưu ý: Nếu ~cntright<pcnt~ thì số cách sẽ bằng ~0~.</p>

• Trường hợp thứ hai (tất cả số nhỏ hơn ~k~ nằm bên trái) xử lý tương tự.

Phần ~(2)~ có thể xử lý với độ phức tạp ~O(n^2)~.

~(3)~: Xét một giá trị ~k~ cụ thể, giả sử cố định một đoạn để "điền" tất cả số từ ~0~ đến ~k~, ta cần đếm số cách điền thỏa mãn theo cách điền (*). Ta sẽ xử lý phần này bằng QHĐ (dynamic programming).

Gọi ~dp[l,r]~ là số cách "điền" các số, bao gồm số ~k~ và các số từ ~0~ đến ~r-l-1~ sao cho thỏa mãn pattern điền (*).

Ta sẽ chia khâu điền làm hai phần, từ đó suy ra công thức QHĐ:

• Điền trước số ~k~ và các số từ ~0~ đến ~t+1~. Ta có thể cố định trước vị trí của ~k~ và ~t+1~ dựa vào đoạn ~[l,r]~ được chọn để điền các số này và đếm số cách bằng tổ hợp, sau đó cộng vào ~dp[l,r]~. Phần tổ hợp cần xét điều kiện phức tạp hơn, xin nhường lại bạn đọc.

• Điền các số còn lại theo thứ tự. Ta chỉ có thể điền số mới bằng cách điền vào bên trái hoặc bên phải đoạn. Vì thế nên khi xét đoạn ~[l,r]~, ta cộng ~dp[l,r]~ cho ~dp[l+1,r]~ và ~dp[l,r-1]~, nếu có thể điền được số ~r-l-1~ vào vị trí ~l~ hoặc ~r~.

Số cách cho một giá trị ~k~ sẽ bằng tổng ~dp[l,r]~ của tất cả cặp ~(l,r)~ có ~r-l=k~. Phần ~(3)~ có thể xử lý với độ phức tạp ~O(n^3)~.

Độ phức tạp: ~O(n^3)~ cho mỗi test case.

Subtask ~4~: Không có ràng buộc gì thêm

Cải tiến phần ~(3)~ từ ý tưởng Subtask 3, liệu có thể "gộp" tất cả lần QHĐ với các giá trị ~k~ khác nhau lại cùng một lúc hay không? Ta có một số nhận xét như sau:

• Trường hợp vị trí điền số ~k~ chưa được điền, ta có thể thay đổi ~k~ tùy ý khi mở rộng đoạn từ khâu sau do ta luôn có ~k=r-l~.

• Trường hợp vị trí điền số ~k~ đã được điền, rõ ràng ~k~ phải là số lớn nhất trong đoạn ~[l,r]~ của mảng ~a'~ nếu thử điền theo cách điền (*), đồng thời vị trí này không được là biên của đoạn. Vì thế sẽ không có trường hợp khi "mở rộng" từ đoạn ~[l,r]~ ra đoạn ~[l-1,r]~ hoặc ~[l,r+1]~, giá trị mới được mở rộng lại lớn hơn tất cả số trước đó. Nói cách khác, vị trí điền ~k~ trong trường hợp này luôn đảm bảo sẽ được cố định.

Từ các nhận xét trên, ta có thể "gộp" tất cả lần QHĐ và chỉ xử lý trong một lần duy nhất, và dựa vào mảng đó để cộng đáp án. Phần xử lý khá phức tạp, xin nhường lại bạn đọc.

Như vậy độ phức tạp cho phần ~(3)~ đã giảm xuống ~O(n^2)~.

Độ phức tạp: ~O(n^2)~ cho mỗi test case.