E-Sum of All Substrings——atcoder379

E - Sum of All Substrings

观察答案的贡献结构，可以发现，不必按照公式给出的方式用双重循环的方式去做，而可以对每个数字单独计算贡献度，记第i位的数字为ai，那么它的贡献度为(i + 1) * (10(0) + 10(1) + ……+10(n - i))，即第i位的数字，可以对后续每个可能的数量级贡献一个(i + 1)倍的值。

我一开始是像下面这样实现的，然后发现这样会漏掉一些值，这样做一个数只会贡献一个他能贡献的最大值，而而其他值就被护理掉了。

public class SumOfAllSubstrings {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String S = sc.next();
        long res = 0;
        for (int i = 0; i < N; i++) {
            int num = S.charAt(i) - '0';
            res = (long) (i + 1) * num + res * 10;
        }
        System.out.println(res);
    }
}

之后受到室友的启发，把每个数乘以对应位数的111……，但是又遇到了溢出的问题，long类型的值都不够保存。

import java.math.BigDecimal;
import java.util.Scanner;

public class SumOfAllSubstrings {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String S = sc.next();
        BigDecimal res = BigDecimal.valueOf(0);
        for (int i = 0; i < N; i++) {
            int num = S.charAt(i) - '0';
            BigDecimal single = BigDecimal.valueOf((i + 1) * num * ((Math.pow(10, N - i) - 1) / 9));
            res = res.add(single);
        }
        System.out.println(res);
    }
}

最后看了一下其他人提交的答案，他是从个位开始一位一位计算最终结果的值的，并且通过把结果保存在字符串中避免了溢出。而为什么能这样一位一位地处理，也与前面保存数据的dig数组脱不开关系，dig数组下标从大到小分别保存个位的贡献值之和，十位的贡献值之和……

public class SumOfAllSubstrings {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String S = sc.next();
        long[] dig = new long[N];
        for (int i = 0; i < N; i++) {
            // 这里保存dig值的方式也是关键
            // 小位数的值是大位数的值的累积，是因为具有大位数的值一定有一个对应的小位数的值
            dig[i] = (long) (i + 1) * (S.charAt(i) - '0');
            if (i > 0) {
                dig[i] += dig[i - 1];
            }
        }
        int i = 0;
        long c = 0;
        StringBuilder sb = new StringBuilder();
        while (i < N || c > 0) {
            // 这里c的更新是一个关键
            // 这里的处理顺序是从后往前也是有讲究的
            if (i < N) {
                c += dig[N - i - 1];
                i++;
            }
            sb.append((c % 10));
            c /= 10;
        }
        System.out.println(sb.reverse());
    }
}