\(\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-forces>}}\)

• Thử các bội của 11 bằng bignum và in ra "YES" nếu tìm được. Có thể dùng nhánh cận để nhanh hơn

\(\color{orange}{\text{Hint 2 <Math>}}\)

• Chúng ta có các tính chất modulo:

\((a + b) \mod c = ((a \mod c) + (b \mod c)) \mod c\)

\((a \times b) \mod c = ((a \mod c) \times (b \mod c)) \mod c\)

• Từ đó suy ra công thức:

\(\overline{ab} \mod c = (a \times 10 + b) \mod c = (((a \times 10) \mod c) + (b \mod c)) \mod c\)

\(\overline{a_1a_2\dots a_n} \mod c = (a_1 \times 10^n + \overline{a_2\dots a_n}) \mod c = (((a_1 \times 10^n) \mod c) + (\overline{a_2\dots a_n} \mod c)) \mod c = (((a_1 \times (10^n \mod c)) \mod c) + (\overline{a_2\dots a_n} \mod c)) \mod c\)

\(\color{orange}{\text{Hint 3 <Dynamic Programming>}}\)

• Chúng ta có thể nhận vào số như một xâu các kí tự số từ đó giải bài

Tách từng số để giải

Lưu ý, nếu nhận vào bằng xâu kí tự thì phải chuyển về dạng số \(s_i = charactor(a_i + integer('0'))\)

\(\color{goldenrod}{\text{<Space Optimization>}}\)

• Chúng ta có thể không cần lưu cả xâu mà có thể xử lí từng kí tự một kể từ trái qua

Sử dụng phép chèn bên phải cùng chữ số \(d\) vào số \(x\): \(new\_x = 10 \times x + d\)

Phần dư của số là \(rem = (10 \times rem + a_i) \mod 11 (\forall i = 1 \dots n)\)

Khi phần dư \(rem = 0\) thì số đó chia hết cho 11

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

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

bool isDigit(char c) { return '0' <= c && c <= '9'; }
int main()
{
    int rem = 0;
    for (char c; isDigit(c = getchar()); rem = (10 * rem + int(c - '0')) % 11);
    cout << (rem == 0 ? "YES" : "NO");
    return 0;
}

\(\color{goldenrod}{\text{<Math>}}\)

• Còn một cách khác đó là sử dụng dấu hiệu chia hết cho 11: Hiệu của (tổng chữ số hàng chẵn) và (tổng chữ số hàng lẻ) là bội của 11

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

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

bool isDigit(char c) { return '0' <= c && c <= '9'; }
int main()
{
    vector<int> sum(2, 0);
    bool p = 0;
    for (char c; isDigit(c = getchar()); sum[p ^= 1] += c - '0');
    cout << ((sum[0] - sum[1]) % 11 == 0 ? "YES" : "NO");
    return 0;
}