Ta cần đếm số lượng các xâu có thể tạo ra tại vị trí \(i\) dựa trên số lượng các xâu có thể tạo ra tại vị trí \(i-1\). Ta cần chọn một kí tự cuối cùng khác với kí tự cuối cùng trước đó (không được trùng), và số lượng các xâu có thể tạo ra sẽ được tính bằng tổng số lượng các xâu có thể tạo ra tại vị trí \(i-1\) với các cặp kí tự khác nhau trước đó và các kí tự cuối cùng khác nhau.

Ta sẽ sử dụng quy hoạch động để giải quyết. gọi \(f[i][j][k]\) là số lượng các xâu có độ dài \(i\) có thể tạo ra trong đó \(i\) là vị trí hiện tại của xâu, \(j\) là là chỉ số của cặp kí tự khác nhau (\(0\), \(1\) hoặc \(2\) tượng trưng cho a,b hoặc c), \(k\) là chỉ số của kí tự cuối cùng trong xâu (\(0\), \(1\), hoặc \(2\) tượng trưng cho a,b hoặc c).

Ta có công thức f[i][j][k] = f[i-1][(j-k+3)%3][l] với mọi \(0 \le l \le 2\) và \(l \neq k\).

Giải thích kĩ hơn về chỉ số:

• \(i-1\) là vị trí trước đó trong xâu.
• \((j-k+3)%3\) là chỉ số của cặp kí tự khác nhau trước đó (đảo ngược vị trí của \(j\) và \(k\) và lấy phần dư khi chia cho \(3\)). Ta chia lấy dư cho \(3\) vì ta lấy giá trị tượng trưng \(0\),\(1\),\(2\) như đã nói ở trên.
• \(l\) là chỉ số của kí tự cuối cùng trong xâu trước đó.

đáp án sẽ là: ans = (ans - f[n-1][sum][i] + mod) % mod với vọi \(i\) từ \(0\) đến \(2\)

Bài này có trường hợp đặc biệt: Xâu có độ dài không quá \(3\).

Nếu xâu ban đầu có độ dài không quá \(3\), tức là chỉ chứa \(3\) kí tự hoặc ít hơn, ta có thể thực hiện tất cả các thao tác để tạo ra tất cả các xâu khác nhau có thể có. Vì số lượng xâu khác nhau có thể tạo ra từ xâu ban đầu là nhỏ nên ta không cần áp dụng quy hoạch động mà chỉ cần tạo ra các xâu mới bằng cách trâu bò.