公式
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.
- Initialize with \(c=0\) and \(i=0\).
- If \(i\lt N\), add \(A_{N-i}\) to \(c\).
- Deduce that the \(10^i\)s place of the answer is the remainder when \(c\) is divided by \(10\).
- Divide \(c\) by \(10\), cutting off the residual, which corresponds to the carry. Increment \(i\) by one.
- 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="")
投稿日時:
最終更新: