E - Sum of All Substrings 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 475 点

問題文

1 から 9 までの数字からなる長さ N の文字列 S が与えられます。

整数の組 (i,j) \ (1\leq i\leq j\leq N) に対して、 f(i,j) を「 S の i 文字目から j 文字目までの連続部分文字列を 10 進法の整数としてみなしたときの値」とします。\displaystyle \sum_{i=1}^N \sum_{j=i}^N f(i,j) を求めてください。

制約

  • 1\leq N\leq 2\times 10^5
  • N は整数
  • S は 1 から 9 までの数字からなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

答えを出力せよ。

入力例 1

3
379

出力例 1

514

答えは f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=3+37+379+7+79+9=514 です。

入力例 2

30
314159265358979323846264338327

出力例 2

369673254065355789035427227741

Score : 475 points

Problem Statement

You are given a string S of length N consisting of digits from 1 through 9.

For each pair of integers (i,j) \ (1\leq i\leq j\leq N), define f(i, j) as the value obtained by interpreting the substring of S from the i-th through the j-th character as a decimal integer. Find \displaystyle \sum_{i=1}^N \sum_{j=i}^N f(i, j).

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • N is an integer.
  • S is a string of length N consisting of digits from 1 through 9.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

3
379

Sample Output 1

514

The answer is f(1,1) + f(1,2) + f(1,3) + f(2,2) + f(2,3) + f(3,3) = 3 + 37 + 379 + 7 + 79 + 9 = 514.

Sample Input 2

30
314159265358979323846264338327

Sample Output 2

369673254065355789035427227741