jkrt의 AND

먼저 조건을 만족하는 양의 정수의 형태를 찾자.

한 자리 양의 정수 $1,2,\ldots,9$는 모두 조건을 만족한다. 실제로 $x$와 $x-1$은 서로 다른 한 자리 수이거나, $x=1$일 때 $0$이므로 공통 부분수열의 길이가 $0$이다.

이제 $x$가 두 자리 이상의 수라고 하자. 만약 $x$의 마지막 자리가 $0$이 아니라면, $x-1$은 $x$의 마지막 자리만 $1$ 감소시킨 수이다. 따라서 마지막 자리를 제외한 앞부분이 그대로 남아 있고, 이 앞부분은 비어 있지 않다. 그러므로 와 은 공통 숫자를 가지며, LCS 길이가 일 수 없다.

따라서 두 자리 이상의 조건을 만족하는 $x$는 반드시 $0$으로 끝난다. $x$의 뒤쪽에 붙은 $0$의 개수를 최대한 많이 떼어

$$x = y \cdot 10^t \quad (t \ge 1)$$

라고 쓰자. 이때 $y$는 $0$으로 끝나지 않는다.

만약 $y$가 두 자리 이상의 수라면, $y-1$은 $y$의 마지막 자리만 $1$ 감소시킨 수이므로 앞부분이 그대로 남는다. 따라서 $x$와 $x-1$ 역시 공통 숫자를 가지게 된다. 그러므로 는 한 자리 수여야 한다.

즉 두 자리 이상의 가능한 수는

$$x = d \cdot 10^t$$

꼴이어야 한다. 여기서 $1 \le d \le 9$, $t \ge 1$이다.

$d=9$이면 $x$의 십진 표기에 $9$가 들어 있고, $x-1$의 뒤쪽에는 $9$들이 생기므로 공통 숫자 $$가 존재한다. 따라서 는 불가능하다. 반대로 이면 의 숫자는 와 뿐이고, 의 숫자는 과 뿐이다. 이 둘은 공통 숫자를 갖지 않으므로 조건을 만족한다.

따라서 조건을 만족하는 수들은 다음 순서로 나열된다.

$$1,2,\ldots,9,\quad 10,20,\ldots,80,\quad 100,200,\ldots,800,\quad 1000,2000,\ldots$$

그러므로 $N \le 9$이면 답은 $N$이다.

$N \ge 10$이면 $A_N$은 다음과 같이 표현된다.

$$A_N = d \cdot 10^e$$

여기서

$$d = ((N-10) \bmod 8) + 1$$

이고,

$$e = \left\lfloor \frac{N-10}{8} \right\rfloor + 1 = \left\lfloor \frac{N-2}{8} \right\rfloor$$

이다.

$N$이 매우 클 수 있으므로 십진 문자열로 처리한다. $d$를 구하기 위해 $N \bmod 8$만 계산하면 된다. $e$는 $N-2$를 문자열에서 계산한 뒤, 이를 로 나누면서 몫을 로 나눈 나머지로 구한다.

마지막으로 페르마의 소정리에 의해

$$10^{998244352} \equiv 1 \pmod {998244353}$$

이므로, $10^e \pmod {998244353}$을 계산할 때 지수 $e$는 $998244352$로 나눈 나머지만 알면 충분하다.

시간 복잡도는 $O(|N|+\log 998244353)$이고, 메모리 사용량은 $O(|N|)$이다.