Official
E - Sum of All Substrings Editorial
by
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\) になります.
この値は筆算の要領で下の桁から計算することができます.
- \(c=0,i=0\) として初期化する.
- \(i\lt N\) のとき \(c\) に \(A_{N-i}\) を加算する.
- 答えの \(10^i\) の位を \(c\) を \(10\) で割った余りとして確定させる.
- \(c\) を \(10\) で割り小数点以下を切り捨てる.ここが繰り上がりに対応する.その後,\(i\) を \(1\) 増やす.
- \(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: