公式

E - Sum of All Substrings 解説 by en_translator


First, consider how the answer can be represented when \(N\) is small. When \(N=3\), the answer is as follows:

\[ \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} \]

More generally, for \(A_i=\displaystyle \sum_{j=1}^i j\times S_j\) the answer is \(\displaystyle \sum_{i=1}^N 10^{N-i}A_i\).

This value can be evaluated from the lower digits in the manner of column addition.

  1. Initialize with \(c=0\) and \(i=0\).
  2. If \(i\lt N\), add \(A_{N-i}\) to \(c\).
  3. Deduce that the \(10^i\)s place of the answer is the remainder when \(c\) is divided by \(10\).
  4. Divide \(c\) by \(10\), cutting off the residual, which corresponds to the carry. Increment \(i\) by one.
  5. Repeat step 2. through 4. while \(i\lt N\) or \(c\gt 0\).

Similar problem: 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="")

投稿日時:
最終更新: