아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

두 정수의 거리

시간 제한3초메모리 제한128 MB

요약
A부터 B까지 모든 순서쌍의 자릿수별 절댓값 차이 합을 구해 1,000,000,007로 나눈 나머지를 출력합니다.
난이도

보통10점 중 7점

유형
동적 계획법, 조합론, 수학
정답자
아직 제출이 없습니다

문제

두 정수의 거리는 같은 자리의 숫자끼리 차이의 절댓값을 모두 더한 값이다. 예를 들어 4561과 3278의 거리는 ∣4−3∣+∣5−2∣+∣6−7∣+∣1−8∣=12|4 - 3| + |5 - 2| + |6 - 7| + |1 - 8| = 12이다. 두 수의 길이가 다르면 짧은 쪽 앞에 0을 붙여 자리를 맞춘다. 그래서 32와 5678의 거리는 ∣0−5∣+∣0−6∣+∣3−7∣+∣2−8∣=21|0 - 5| + |0 - 6| + |3 - 7| + |2 - 8| = 21이다.

두 정수 AA와 BB가 주어졌을 때, 구간 [A,B][A, B]에 속하는 모든 순서쌍 (x,y)(x, y)의 거리의 합을 구하는 프로그램을 작성하시오. 순서를 바꾼 (y,x)(y, x)도 따로 세고, 거리가 0인 x=yx = y도 포함한다.

입력

첫째 줄에 두 정수 AA와 BB가 빈 칸을 사이에 두고 주어진다. (1≤A≤B≤10500001 \le A \le B \le 10^{50000})

출력

첫째 줄에 구간 [A,B][A, B]에 속하는 모든 순서쌍의 거리의 합을 출력한다. 답이 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

예제3

  1. 예제 1

    입력
    1 5
    
    예상 출력
    40
    
  2. 예제 2

    입력
    288 291
    
    예상 출력
    76
    
  3. 예제 3

    입력
    1000000 10000000
    
    예상 출력
    581093400