Editorial for Tèo và xâu đối xứng (Bản không dễ)

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lời giải sẽ dùng các nhận xét từ lời giải ở bản dễ, cụ thể:

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$ .
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$ .

Để giải quyết được bài toán, chúng ta xét một bản dễ hơn như sau:

Cho một xâu $s$ $(| s | \leq 2 \cdot 10^{5})$ , hãy đếm xem có bao nhiêu cặp $(l, r)$ $(l \leq r)$ sao cho xâu $s_{l} s_{l + 1} . . . s_{r}$ là xâu đối xứng và có độ dài lẻ.

Vì $| s | \leq 2 \cdot 10^{5}$ nên chúng ta không thể dùng quy hoạch động để giải quyết bài toán, cho nên ta cần một cách nhanh hơn để đếm số cặp.

Nhận thấy rằng, nếu xâu $s$ là xâu đối xứng thì xâu $s_{2} s_{3} . . . s_{| s | - 1}$ cũng là xâu đối xứng. Cho nên, với mỗi vị trí $i$ , ta tìm độ dài $l e n$ lớn nhất sao cho xâu $s_{i - l e n} s_{i - l e n + 1} . . . s_{i} . . . s_{i + l e n - 1} s_{i + l e n}$ là xâu đối xứng.

Để tìm được giá trị $l e n$ , chúng ta có hai cách: chặt nhị phân và dùng hash để kiểm tra trong $O (n \log_{2} n)$ , hoặc dùng thuật toán Manacher trong $O (n)$ .

Như vậy, đáp án của bài toán trên chỉ là tổng $l e n + 1$ của mọi $i$ .

Trở lại với bài toán chính, không chỉ kiểm tra xâu đối xứng mà chúng ta cần kiểm tra thêm xâu có chia hết cho $2, 3, 5$ .

Với mỗi $i$ , ta chỉ xét những j $(0 \leq j \leq l e n)$ sao cho tổng chữ số của $s_{i - j} s_{i - j + 1} . . . s_{i} . . . s_{i + j - 1} s_{i + j}$ chia hết cho $3$ và $s_{i + j} = 0$ .

Chúng ta chia $s_{i - j} s_{i - j + 1} . . . s_{i} . . . s_{i + j - 1} s_{i + j}$ thành $3$ phần:

Phần đầu: $s_{i - j} s_{i - j + 1} . . . s_{i - 1}$ .
Phần giữa: $s_{i}$ .
Phần đuôi: $s_{i + 1} . . . s_{i + j - 1} s_{i + j}$ .

Gọi tổng chữ số của $3$ phần lần lượt là $s u m 1$ , $s u m 2$ và $s u m 3$ . Chúng ta có nhận xét như sau:

Vì xâu đối xứng nên $s u m 1 = s u m 3$ . Vì vậy điều kiện để xâu chia hết cho $3$ là $s u m 2 + s u m 3 \cdot 2 \equiv 0 \mod 3$ .

Sau khi thử hết các giá trị modulo, ta rút ra được $s u m 2 = s u m 3$ .

Như vậy, với mỗi $i$ , chúng ta cần đếm số $j$ sao cho thỏa mãn:

$0 \leq (j - i) \leq l e n$
$s_{j} = 0$
$s_{i + 1} + s_{i + 2} + . . . + s_{j} \equiv s_{i} \mod 3$

Việc đếm $j$ có thể giải quyết bằng tổng tiền tố.

ĐPT: $O (n)$ nếu dùng Manacher, $O (n \log_{2} n)$ nếu dùng hash.

Comments

Please read the guidelines before commenting.

There are no comments at the moment.