문자열 형식의 숫자가 있고 s의 모든 부분 문자열의 합을 찾아야 한다고 가정합니다. 대답은 매우 클 수 있으므로 결과 모듈로 10^9+7을 반환합니다.
따라서 입력이 s ="268"과 같으면 하위 문자열이 "2", "6", "8", "26", "68" 및 "268"이기 때문에 출력은 378이 됩니다. 총합은 378입니다. .
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 남 :=10^9 + 7
- sum_val :=0
- B :=1
- res :=0
- 범위 크기가 s - 1에서 0까지의 i에 대해 1 감소, do
- res :=(res + s[i] * B *(i + 1)) mod M의 숫자 값
- sum_val :=sum_val - s[i]의 숫자 값
- B :=(B * 10 + 1) 모드 M
- 반환 결과
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(s): M = 10 ** 9 + 7 sum_val = 0 B = 1 res = 0 for i in range(len(s) - 1, -1, -1): res = (res + int(s[i]) * B * (i + 1)) % M sum_val -= int(s[i]) B = (B * 10 + 1) % M return res s = "268" print(solve(s))
입력
"268"
출력
378