Subtask 1

Vì ~|s| \leq 18~, nên với mỗi xâu con chúng ta có thể biểu diễn xâu dưới dạng long long, rồi kiểm tra thuần bằng phép modulo.

ĐPT: ~O(|s|^3)~

Subtask 2

Vì ~|s| \leq 10^2~, nên khi biểu diễn dưới dạng long long sẽ bị tràn số, dẫn đến việc kiểm tra không chính xác. Vì vậy, ta cần một cách nhanh hơn để kiểm tra một số có chia hết cho ~2, 3, 5~ hay không.

• Vì chia hết cho ~2~ và ~5~, nên số đó phải chia hết cho ~10~, suy ra chữ số tận cùng luôn là ~0~.

• Để kiểm tra tính chia hết cho ~3~, chúng ta nhận xét với mỗi số chia hết cho ~3~ thì tổng số chữ số của nó luôn chia hết cho ~3~, việc chứng minh mình xin nhường cho bạn đọc.

Kết hợp hai điều kiện này, chúng ta có thể dễ dàng kiểm tra một số có chia hết cho ~2, 3, 5~ mà không cần biểu diễn dưới dạng long long.

ĐPT: ~O(|s|^3)~

Subtask 3

Thay vì kiểm tra một xâu ~t~ là xâu đối xứng hay không trong ~O(t)~. Chúng ta có thể kiểm tra bằng phương pháp quy hoạch động.

Gọi ~dp_{l, r}=1~ nếu xâu ~s_l s_l+1 ... s_r~ là xâu đối xứng, ~dp_{l, r}=0~ nếu không.

Khi đó, ta có công thức truy hồi:

• Khi ~l=r~, ~dp_{l,r}=1~.
• Khi ~r = l + 1~, ~dp_{l, r}=1~ nếu ~s_l=s_r~.
• Nếu không thỏa hai điều kiện trên, ~dp_{l, r}=1~ nếu ~s_l=s_r~ và ~dp_{l+1, r-1}=1~.

Việc tính mảng ~dp~ có thể xử lý bằng duyệt hoặc đệ quy và kiểm tra xâu có chia hết cho ~3~ có thể xử lý bằng mảng tiền tố.

ĐPT: ~O(|s|^2)~