{"code":"dyslexia","name":"Đọc nhầm đề (phiên bản không có base64)","description":"Ở một kỳ thi Codeforces không gần đây, bạn Hesll một lần nữa lại đọc nhầm đề mà quên mất rằng, nó chỉ là bài B mà thôi. Hesll đọc nhầm đề bài thành như sau:\r\n\r\nVới một xâu nhị phân $X$ bất kỳ, gọi $x$ và $y$ lần lượt là số lượng chữ số $1$ và $0$ trong xâu nhị phân đó. Khi đó, trọng số $w$ của xâu $X$ là:\r\n\r\n$$w(X) =\r\n\\left\\{\r\n\t\\begin{array}{ll}\r\n\t\txy  & \\text{nếu } x > 0 \\ \\text{và} \\ y > 0 \\\\\r\n\t\tx^2  & \\text{nếu } x > 0 \\ \\text{và} \\ y = 0 \\\\\r\n\t\ty^2  & \\text{nếu } x = 0 \\ \\text{và} \\ y > 0 \\\\\r\n\t\\end{array}\r\n\\right.$$\r\n\r\nCho xâu $S$ có $n = |S|$ là độ dài xâu. Một xâu được gọi là xâu con liên tiếp (gọi tắt là xâu con) của xâu $S$ nếu nó có thể được tạo bằng cách xóa đi một số ký tự đầu tiên và cuối cùng của xâu. Khi đó, xâu con bắt đầu từ vị trí $l$, kết thúc tại vị trí $r$ được gọi là xâu $S_{l, r}$ $(0 \\le l \\le r < n)$.\r\n\r\nVí dụ, `abc` là xâu con liên tiếp của `dabce` nhưng không phải là xâu con liên tiếp của `adbce`.\r\n\r\nCho xâu nhị phân $S$ có độ dài $n$. Tính $\\sum\\limits_{l=0}^{n-1} \\sum\\limits_{r=l}^{n-1} w(S_{l,r})$, hay nói cách khác là tổng trọng số của mọi xâu con liên tiếp của $S$.\r\n\r\n> **Not-fun fact:** Bài này được ra trong Round 6 LQDOJ CUP 2023. \r\n> Mình rất cay là tự nhiên mình bị ép đẩy $n = 10^7$ để tránh thuật $\\mathcal{O}(n \\log n)$, và vì vậy nên đầu vào phải ép về dạng base64.\r\n> Xong mình đòi code $\\mathcal{O}(n)$ thì đếch ai code cho mình cả.\r\n> Cuối cùng lúc đi thi thì rất nhiều bạn code lỗi phần base64.\r\n> Bài này là bài mình tâm đắc nhất, nhưng cuối cùng fail vl huhu.\r\n\r\n#### Input\r\n- Một dòng duy nhất chứa một xâu nhị phân có độ dài $n \\leq 10^5$, chỉ gồm các ký tự 0 và 1.\r\n\r\n#### Output\r\n- In ra đáp án của bài toán.\r\n#### Scoring\r\n - Subtask $1$ ($20\\%$ số điểm): $n \\leq 300$.\r\n - Subtask $2$ ($25\\%$ số điểm): $n \\leq 5 \\times 10^3$.\r\n - Subtask $3$ ($10\\%$ số điểm): $n \\leq 10^5$, toàn bộ các ký tự của $S$ đều giống nhau.\r\n - Subtask $4$ ($15\\%$ số điểm): $n \\leq 10^5$, tồn tại duy nhất một vị trí $i$ sao cho $S_i \\neq S_{i + 1}$ ($0 \\le i < n-1$).\r\n - Subtask $5$ ($30\\%$ số điểm): Không có ràng buộc gì thêm.\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        0110\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        18\r\n        ```\r\n    ??? warning \"Note\"\r\n        <center>\r\n        \r\n        | Xâu con | Trọng số | Xâu con | Trọng số | Xâu con | Trọng số | Xâu con | Trọng số |\r\n        |---|---|---|---|---|---|---|---|\r\n        |`0` | $1$ | `01` | $1$ | `011` | $2$ | `0110` | $4$ |\r\n        |`1` | $1$ | `11` | $4$ | `110` | $2$ |      |   |\r\n        |`1` | $1$ | `10` | $1$ |     |   |      |   |\r\n        |`0` | $1$ |    |   |     |   |      |   |\r\n        \r\n        </center>","points":1900.0,"partial":false,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}