Pi Problem

$P=998\,244\,353$이라 하자. $a$의 자릿수가 $d$이면 $\mathrm{rep}(a,b)$는 다음과 같다.

$$\mathrm{rep}(a,b)=a\sum_{k=0}^{b-1}10^{dk}=a\frac{10^{db}-1}{10^d-1}.$$

$1\leq d\leq10$에서 $10^d-1$은 $P$의 배수가 아니므로 모듈러 역원으로 나눗셈을 계산할 수 있다. $G_d(b)$를 위 식의 등비급수 부분을 $P$로 나눈 나머지라고 하자.

$A_i$의 자릿수를 $d_i$라 하자. 인덱스 $i$가 왼쪽 끝인 모든 쌍의 곱은 다음과 같다.

$$A_i^{N-i}\prod_{j=i+1}^{N}G_{d_i}(A_j)$$

따라서 오른쪽에서 왼쪽으로 순회하면서 자릿수 $d$별 접미 곱 $S_d=\prod_{j>i}G_d(A_j)$를 유지한다. 먼저 정답에 $A_i^{N-i}S_{d_i}$를 곱하고, 그다음 모든 $S_d$에 $G_d(A_i)$를 곱한다. 이 순서여야 $(i,i)$가 포함되지 않는다.

$10^d-1$의 역원은 미리 구한다. $G_d(A_i)$를 계산할 때는 $x=10^{A_i}\bmod P$를 한 번 구한 뒤 $x^1,x^2,\cdots,x^{10}$을 차례로 곱해 사용한다. 한 케이스의 시간 복잡도는 $O(N(10+\log N+\log\max A_i))$, 공간 복잡도는 $O(N)$이다.

증명

각 $i$를 처리하기 직전에 $S_d$는 정확히 $j>i$인 원소들의 $G_d(A_j)$를 모두 곱한 값이다. 처음에는 오른쪽 원소가 없으므로 모든 $S_d=1$이다. $i$의 기여분을 정답에 곱한 뒤 $G_d(A_i)$를 $S_d$에 곱하면 다음 인덱스에 대해서도 불변식이 유지된다.

각 쌍 $(i,j)$는 왼쪽 끝 $i$를 처리할 때 $A_i$ 한 번과 $G_{d_i}(A_j)$ 한 번으로 포함된다. 다른 단계에서는 포함되지 않는다. 따라서 마지막 값이 요구한 모든 쌍의 곱이다.

서브태스크 1에서는 수를 직접 이어 붙여도 된다. 서브태스크 2에서는 모든 쌍을 순회하며 등비급수 식으로 계산한다. 서브태스크 3에서는 자릿수가 항상 $1$이므로 접미 곱 하나만 관리한다. 전체 조건에서는 자릿수 $1$부터 $10$까지 각각 접미 곱을 관리한다.

Solution written by GPT5