SPSUM - Sum

Tác giả: hieult

Ngôn ngữ: Java

import java.util.*;
import java.math.*;
import java.io.*;

public class Main {
    static int a[] = new int[105];
    static int n;
    static String s;
    static BigInteger B[] = new BigInteger[105];
    static BigInteger f[] = new BigInteger[105];
    static BigInteger g[] = new BigInteger[105];
    
    public static void init(){
        for(int i = 0; i < n; i++){
            a[i] = Integer.parseInt(s.substring(i, i + 1));
        }
        f[0] = BigInteger.ONE;
        g[0] = BigInteger.ZERO;
        for(int i = 1; i <= n; i++) {
            f[i] = f[i - 1].multiply(BigInteger.valueOf(10));
            g[i] = f[i - 1].multiply(BigInteger.valueOf(i));
        }
        
        B[n] = BigInteger.ZERO;
        for(int i = n - 1; i >= 0; i--){
            B[i] = B[i + 1].add(f[n - i - 1].multiply(BigInteger.valueOf(a[i])));
        }
    }
    
    public static BigInteger cal(int id, int num){
        BigInteger res = BigInteger.ZERO;
        if(id == n) return res;
        for(int i = 0; i < a[id]; i++){
            if(i == num) res = res.add(f[n - id - 1]);
            res = res.add(g[n - id - 1]);
        }
        
        if(a[id] == num){
            res = res.add(B[id + 1].add(BigInteger.ONE));
        }
        return res.add(cal(id + 1, num));
    }
    
    public static void main(String args[]) throws Exception{
        Scanner sc = new Scanner(System.in);
        s = sc.next();
        n = s.length();
        init();
        BigInteger res = BigInteger.ZERO, ret;
        for(int i = 1; i <= 9; i++){
            ret = cal(0, i);
            res = res.add(ret.multiply(BigInteger.valueOf(i)));
        }
        System.out.println(res);
    }
}

Download