\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-force>}}\)

• Thử từng đoạn một và kiểm tra tính chia hết cho 2

Số chia hết cho 2 thì sẽ có chữ số tận cùng chẵn

Ta chỉ cần đếm số lượng dãy \(s[l..r]\) mà \(s[r]\) chẵn là được

\(\color{orange}{\text{Hint 2 <Online-Solving>}}\)

• Nhận thấy rằng khi \(s[r]\) chẵn thì \(\forall 1 \leq l \leq r\) ta có \(s[l..r]\) cũng là số chẵn

Giải thích: \(n \equiv 0 \pmod 2 \Leftrightarrow n + 10 \times z \pmod 2\) với \(n, z \in \mathbb{Z}\)

Vậy duyệt từng chữ số, nếu chữ số hiện tại ở vị trí \(r\) là chẵn thì từ đầu xâu tới hiện tại đều chẵn

\(\color{orange}{\text{Hint 3 <Space-Optimization>}}\)

• Chúng ta có thể không cần lưu xâu và chỉ cần nhận từng kí tự

\(\color{green}{\text{Preference AC Code }}\): Online Solving

\(^{^{\color{purple}{\text{Complexity : }} O(n)\ \color{purple}{\text{time}}\ ||\ O(1)\ \color{purple}{\text{memory}}}}\)

bool isDigit(char c) { return '0' <= c && c <= '9'; }
int main()
{
    int n;
    cin >> n;

    ll res = 0;
    char c;
    while (!isDigit(c = getchar()));
    for (int i = 1; i <= n; ++i, c = getchar())
    {
        if ((c - '0') % 2 == 0)
        {
            res += i;
        }
    }
    cout << res;
    return 0;
}

\(\color{orange}{\text{Another Approach}}\)

• Chúng ta có thể sử dụng mảng đánh dấu để kiểm tra nhanh hơn (có 5 số)

\(\color{orange}{\text{Another Approach}}\)

• Chúng ta có thể tiếp cận ngược tiếp cận ở \(\color{orange}{\text{Hint 2 <Online-Solving>}}\)

Chúng ta sẽ lưu tất cả các vị trí số chẵn, và khi duyệt qua từng phần tử đếm xem có bao nhiêu phần tử có vị trí lớn hơn hoặc bằng hiện tại mà chẵn