AtCoder-abc379-E-Sum of All Substrings

题目大意

对于一个长度为2e5的数字字符串，找出所有的排列，类似于找两个下标(i,j)得到从下标i～下标j组成的数，然后计算这些组合的总和。

解题思路

这是看B站上大佬分享的思路：数位贡献法，就是计算每一位都是由谁来贡献的值；例如：

3 7 9
对于个位：
9 79 379 9＊3 27
7 37 7＊2 14
3 3 3
十位：
79 379 7＊2 14
37 3 3
百位：
379 3 3

那么可以发现相邻数位之间是存在关系的，低位就是将去掉第一行然后讲下面的每一行都加上当前数紧挨着的下一位，而有些值会被计算多次，那么可以通过差分的形式来计算总和，这样看的话，当前位的值都会为接下来的每一位进行贡献。

AC代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 2e6+10;
int n;
ll a[N],b[N];

int main() {

    cin>>n;
    string s;
    cin>>s;
    for(int i = 1;i <= n;i++) {
        a[i] = s[i-1] - '0';
    }
    for(int i = n;i >= 1;i--) {
        b[i] = 1ll*i*a[i];
    }
    for(int i = 1;i <= n;i++) {
        b[i] += b[i-1];
    }
    for(int i = n;i >= 1;i--) {
        b[i-1] += b[i] / 10;
        b[i] %= 10;
    }
    if(b[0] != 0) cout<<b[0];
    for(int i = 1;i <= n;i++) {
        cout<<b[i];
    }
    cout<<endl;
    return 0;
}

// 3 7 9
// 个位：9 79 379  9＊3
//       7 37      7＊2
//       3         3
// 44
// 十位：79 379    7＊2
//       37        3
// 17
// 百位：379       3
// 3

// 3 14 27
// 3 17 44

// 3*100+17*10+44 = 300 + 170 + 44 = 514