이라 하자. 의 자릿수가 이면 는 다음과 같다.
에서 은 의 배수가 아니므로 모듈러 역원으로 나눗셈을 계산할 수 있다. 를 위 식의 등비급수 부분을 로 나눈 나머지라고 하자.
의 자릿수를 라 하자. 인덱스 가 왼쪽 끝인 모든 쌍의 곱은 다음과 같다.
따라서 오른쪽에서 왼쪽으로 순회하면서 자릿수 별 접미 곱 를 유지한다. 먼저 정답에 를 곱하고, 그다음 모든 에 를 곱한다. 이 순서여야 가 포함되지 않는다.
의 역원은 미리 구한다. 를 계산할 때는 를 한 번 구한 뒤 을 차례로 곱해 사용한다. 한 케이스의 시간 복잡도는 , 공간 복잡도는 이다.
증명
각 를 처리하기 직전에 는 정확히 인 원소들의 를 모두 곱한 값이다. 처음에는 오른쪽 원소가 없으므로 모든 이다. 의 기여분을 정답에 곱한 뒤 를 에 곱하면 다음 인덱스에 대해서도 불변식이 유지된다.
서브태스크 1에서는 수를 직접 이어 붙여도 된다. 서브태스크 2에서는 모든 쌍을 순회하며 등비급수 식으로 계산한다. 서브태스크 3에서는 자릿수가 항상 이므로 접미 곱 하나만 관리한다. 전체 조건에서는 자릿수 부터 까지 각각 접미 곱을 관리한다.
Solution written by GPT5
각 쌍 는 왼쪽 끝 를 처리할 때 한 번과 한 번으로 포함된다. 다른 단계에서는 포함되지 않는다. 따라서 마지막 값이 요구한 모든 쌍의 곱이다.
