E. 最终倒计时
你身处一个即将爆炸并毁灭地球的核实验室。你必须在最终倒计时归零之前拯救地球。

倒计时由 $n$（$1 \le n \le 4\times 10^5$）个机械指示器组成，每个指示器显示一个十进制数字。你注意到，当倒计时的状态从 $x$ 变为 $x-1$ 时，并不是一步完成的。相反，每改变一个数字需要 $1$ 秒。

例如，如果倒计时显示 $42$，那么它将在 $1$ 秒内变为 $41$，因为只更改了一个数字；但如果倒计时显示 $2300$，那么它将在 $3$ 秒内变为 $2299$，因为最后三个数字都发生了更改。

请计算倒计时归零还需要多少秒。

---

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。
每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 4\times 10^5$）。
第二行包含一个长度为 $n$ 的字符串，表示倒计时的当前状态。保证至少有一个数字不是 $0$。
所有测试用例的 $n$ 之和不超过 $4\times 10^5$。

---

输出格式

对于每个测试用例，输出一个整数（不含前导零），表示倒计时归零所需的秒数。注意这个数字可能非常大。

---

示例

输入：

5
2
42
5
12345
2
99
4
0005
27
456480697259671309012631002

输出：

46
13715
108
5
507200774732968121125145546

---

题目分析

关键观察

将倒计时显示的数字记为 $s$（十进制）。当数字从 $s$ 逐步减到 $0$ 时，考虑从右向左数第 $i$ 位（个位为第 $0$ 位）。这一位上的指示灯每经过 $10^i$ 次变化就会翻转一次（因为每减少 $10^i$，该位就会循环一周）。因此，第 $i$ 位翻转的总次数等于 $\left\lfloor \frac{s}{10^i} \right\rfloor$。

总时间等于所有位翻转次数之和：

$$\text{ans} = \sum_{i=0}^{n-1} \left\lfloor \frac{s}{10^i} \right\rfloor $$

公式化简

设 $s$ 的十进制数字从高位到低位为 $s_{n-1} s_{n-2} \dots s_0$（$s_0$ 是个位）。那么 $\left\lfloor s / 10^i \right\rfloor$ 恰好等于从第 $i$ 位到最高位组成的数字（即后缀数字）。因此：

$$\text{ans} = \sum_{i=0}^{n-1} \text{suffix}_i$$

其中 $\text{suffix}_i = \sum_{j=i}^{n-1} s_j \cdot 10^{\,j-i}$。

交换求和顺序：

$$\text{ans} = \sum_{j=0}^{n-1} s_j \cdot \sum_{i=0}^{j} 10^{\,j-i} = \sum_{j=0}^{n-1} s_j \cdot \underbrace{11\ldots1}_{j+1\text{个}1} $$

这个形式直接计算需要高精度，但可以通过模拟竖式加法高效完成。

高效算法

将所有后缀数字按个位对齐后相加，等价于：

• 个位：所有后缀的个位数字之和 = $s_0 + s_1 + \dots + s_{n-1}$
• 十位：所有后缀的十位数字之和 = $s_1 + s_2 + \dots + s_{n-1}$
• 百位：$s_2 + s_3 + \dots + s_{n-1}$
• ……

因此，我们可以先计算后缀和数组 $a[k]$，其中 $a[k]$ 表示从第 $k$ 位到最高位的数字之和（数字本身的和，不是数值）。然后从低位到高位逐位累加，处理进位。

具体步骤（参考标程）：

1. 反转字符串，使下标 $0$ 对应个位。
2. 计算后缀和数组 $a$：$a[i] = a[i+1] + (s[i] - '0')$（从高位向低位，即从 $n-1$ 到 $0$）。
3. 初始化进位 $c = 0$，结果字符串 $res$ 为空。
4. 遍历 $i = 0$ 到 $n-1$：
   • $c \leftarrow c + a[i]$
   • $res$ 末尾添加 $c \bmod 10$ 的字符
   • $c \leftarrow \lfloor c / 10 \rfloor$
5. 若最后 $c > 0$，将 $c$ 转换为字符串添加到 $res$ 末尾（$c$ 一定是一位数，因为总和小于 $10^{n+1}$）。
6. 反转 $res$，去掉前导零后输出。

正确性证明

竖式加法中，第 $i$ 位（从个位起）的贡献正是所有后缀在该位上的数字之和，即 $a[i]$。累加进位 $c$ 并逐位输出，得到的就是所有后缀数字的和。由于后缀数字的个数为 $n$，每个最多 $n$ 位，总和位数不超过 $n+1$，因此进位处理正确。

---

复杂度

每个测试用例 $O(n)$ 时间，$O(n)$ 额外空间。总 $n$ 不超过 $4\times 10^5$，完全可行。

---

标程代码（已注释）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        reverse(s.begin(), s.end());          // 反转，使下标0对应个位
        vector<int> a(n + 1, 0);              // 后缀和数组，多一位方便计算
        for (int i = n - 1; i >= 0; --i) {
            a[i] = a[i + 1] + (s[i] - '0');   // 从高位向低位累加数字和
        }
        string res;
        int carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += a[i];                    // 加上当前位的数字和
            res.push_back(char(carry % 10 + '0')); // 当前位的数字
            carry /= 10;                      // 进位
        }
        // 处理最后的进位（可能有多位，但实际最多一位）
        while (carry > 0) {
            res.push_back(char(carry % 10 + '0'));
            carry /= 10;
        }
        // 去掉前导零并反转回正常顺序
        while (res.back() == '0') res.pop_back();
        reverse(res.begin(), res.end());
        cout << res << "\n";
    }
    return 0;
}

---

总结

本题的核心是将总时间转化为所有后缀数字的和，然后通过后缀和与竖式加法在 $O(n)$ 时间内求出结果，避免了直接处理巨大整数。这种方法既简洁又高效。