Official

E - Sum of All Substrings Editorial by toam


まずは \(N\) が小さいときに答えがどのように表されるかを考えてみましょう.\(N=3\) のときは答えは次のようになります:

\[ \begin{aligned} &f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3) \\ =& (S_1)+(10S_1+S_2)+(100S_1+10S_2+S_3)+(S_2)+(10S_2+S_3)+(S_3)\\ =& 10^2(S_1)+10^1(S_1+2S_2)+10^0(S_1+2S_2+3S_3) \end{aligned} \]

より一般に,\(A_i=\displaystyle \sum_{j=1}^i j\times S_j\) として答えは \(\displaystyle \sum_{i=1}^N 10^{N-i}A_i\) になります.

この値は筆算の要領で下の桁から計算することができます.

  1. \(c=0,i=0\) として初期化する.
  2. \(i\lt N\) のとき \(c\)\(A_{N-i}\) を加算する.
  3. 答えの \(10^i\) の位を \(c\)\(10\) で割った余りとして確定させる.
  4. \(c\)\(10\) で割り小数点以下を切り捨てる.ここが繰り上がりに対応する.その後,\(i\)\(1\) 増やす.
  5. \(i\lt N\) または \(c\gt 0\) である限り 2. から 4. の流れを繰り返す.

類題:ABC233E (Σ[k=0..10^100]floor(X/10^k))

n = int(input())
s = input()
a = [(i + 1) * int(s[i]) for i in range(n)]
for i in range(1, n):
    a[i] += a[i - 1]
i = 0
c = 0
ans = []
while i < n or c > 0:
    if i < n:
        c += a[n - 1 - i]
    ans.append(c % 10)
    c //= 10
    i += 1
print(*ans[::-1], sep="")

posted:
last update: