菜王的 blog

思路

首先，

$\sum_{k=0}^{10^{100}} \lfloor \dfrac{x}{10^k} \rfloor$

相当于

$\sum_{k=0}^{\log_{10} x} \lfloor \dfrac{x}{10^k} \rfloor$

因为如果 $k > \log_{10} x$，$\lfloor \dfrac{x}{10^k} \rfloor = 0$，对答案没有贡献。

然后，$\lfloor \dfrac{x}{10^k} \rfloor$ 相当于取 $x$ 的前 $\log_{10}(x) - k$ 位，这个手推一下就出来了。

所以，

$\sum_{k=0}^{\log_{10} x} \lfloor \dfrac{x}{10^k} \rfloor$

相当于求 $x$ 的前 $1$ 位 $+$ $x$ 的前 $2$ 位 $+$ $x$ 的前 $3$ 位 $+ \ ...$

将竖式列出来，就变成这样：

$(x = 114514)$

       1
      11
     114
    1145
   11451
+ 114514

竖着看每一列，设 $a_i$ 为 $x$ 的第 $i$ 位，第 $i$ 列的和就为 $\sum_{k = 1}^{i} a_k$。

我们发现，这不就是前缀和吗？

求出每一列的前缀和，一个一个从后往前进位即可。

代码

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <stack>

using namespace std;

char ch[500001];
int n, sum[500001];
stack<int> st;
int main(){
	scanf("%s", ch + 1);
	n = strlen(ch + 1);
	for (int i = 1;i <= n;i ++) sum[i] = sum[i - 1] + (ch[i] ^ 48); // 前缀和
	for (int i = n;i >= 1;i --){
		sum[i - 1] += sum[i] / 10; // 进位
		st.push(sum[i] % 10); // 当前位
	}
	st.push(sum[0]); // 如果进多了一位
	while (st.size() && !st.top()) st.pop(); // 去掉前导 0
	while (st.size()) printf("%d", st.top()), st.pop(); // 倒序输出
}