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

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

무지개 수

시간 제한1초메모리 제한512 MB

요약
자릿수가 최대 100000인 두 경계 사이에서 이웃한 자리가 서로 다른 수의 개수를 998244353으로 나눈 나머지로 구한다.
난이도

어려움10점 중 8점

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

문제

무지개 수란, 1010진법으로 표현했을 때 앞에 불필요한 0이 없고 이웃한 두 자리가 서로 다른 정수를 말한다.

두 경계 LL과 UU가 주어질 때, LL 이상 UU 이하인 무지개 수의 개수를 구하시오.

입력

첫째 줄에 정수 LL (1≤L<101051 \le L < 10^{10^5})이 주어진다. 이는 하한이다.

둘째 줄에 정수 UU (1≤U<101051 \le U < 10^{10^5})가 주어진다. 이는 상한이다.

L≤UL \le U임이 보장된다. 범위가 잘못 적힌 것이 아니다. LL과 UU는 최대 10510^5자리까지 될 수 있다.

출력

LL 이상 UU 이하인 무지개 수의 개수를 한 줄에 출력한다. 이 수는 매우 클 수 있으므로 998 244 353998\,244\,353으로 나눈 나머지를 출력한다.

예제2

  1. 예제 1

    입력
    1
    10
    
    예상 출력
    10
    
  2. 예제 2

    입력
    12345
    65432
    
    예상 출력
    35882