백준 17415번 Huge Integer!

문제

N개의 $(a_i, b_i)$쌍이 주어졌을 때, 다음과 같은 수 $\lambda$를 $K$로 나눈 나머지를 구하는 것이다.

$$
\lambda = \underbrace{a_1 \cdots a_1}_{b_1} \underbrace{a_2 \cdots a_2}_{b_2} \cdots \cdots \underbrace{a_{n-1} \cdots a_{n-1}}_{b_{n-1}} \underbrace{a_n \cdots a_n}_{b_n}
$$

각 $a_i$를 $b_i$개씩 이어붙인 숫자를 K로 나눈 나머지를 구한다고 생각하면 된다.

서브태스크 1의 경우 $b_i$의 총 합이 백만으로 나이브한 방식으로 그냥 숫자를 붙여나가면 맞을 수 있다.

서브태스크 2는 당연히 이런 방식으로 접근하면 시간초과가 난다. 먼저, $a_{i-1}$까지 처라한 숫자 $\lambda^{(i-1)}$가 있다고 하자. $\lambda^{(i)}$는 다음과 같은 식으로 구할 수 있다.

$$
\lambda^{(i)} = \lambda^{(i-1)}*10^{b_i}+\underbrace{a_i \cdots a_i}_{b_i}
$$

물론 이 문제에서 모든 연산은 $mod\;K$가 적용된다. 먼저 떠올릴 법한 것은 1로만 이루어진 $2^i$길이의 숫자들을 모조리 계산 해둔다. $B_i$길이의 숫자는 $\lambda$를 만드는 것과 같은 방식을 사용하여 계산해내는 것이다. 미리 계산해둔 숫자로 $b_i$길이의 숫자를 만드는 것은 분할정복을 이용한 거듭제곱과 같은 방식으로 하면 된다. 이를 이용하면 $O(log\;b_i)$만에 가능하다. 그러나 $0 \le b_i \le 10^{18}$이고 $N \le 2*10^6$으로 대략적인 연산량이 10억이 넘어간다. 요즘 컴퓨터가 빠르다고 해도 모듈로 연산으로 10억이 넘어가는 프로그램이 1초만에 통과하긴 힘들다. 물론 실제로도 시간초과가 난다. 다른 방법이 필요하다.

$\lambda$를 빠르게 구하기 위해서는 10의 거듭제곱과 1을 쭉 이어붙인 숫자의 $mod\; K$값이 필요하다. 이 두가지를 각각 $\alpha_n$, $\beta_n$이라는 수열로 놓자. 그러면 그 수열의 점화식은 아래와 같다.

$$
\begin{aligned}
\alpha_{n+1} &= 10 \alpha_n, \alpha_0 = 1 \\
\beta_{n+1} &= 10 \beta_n + 1, \beta_1 = 1
\end{aligned}
$$

선형점화식을 가진 수열에 모듈로 연산을 취하면 어느 시점부터 주기를 갖게 된다. 이 점을 이용해서 사이클이 시작하는 순간과 사이클의 길이를 각각 구하면 $(a_i,b_i)$가 들어왔을 때 필요한 숫자를 상수 시간안에 구할 수 있다. $ { \alpha_n\;mod\;K }$를 ${\gamma_n}$이라 하고 사이클의 길이는 $c$, 사이클이 시작하는 위치가 $s$라고 한다면 $\gamma_{b_i}=10^{b_i}$는 아래와 같이 구할 수 있다.
$$
\gamma_{b_i} = \gamma_{s+(b_i-s)\;mod\;c}\quad if \quad b_i\ge s
$$

$b_i$가 $s$보다 작을 때는 그냥 구해주면 된다.

수열에서 사이클이 시작하는 순간과 사이클의 길이만 미리 구해두면 $O(1)$만에 $b_i$번째 항을 구할 수 있다. 사이클을 찾는데는 최대 K만큼 걸리므로 총 실행시간은 $O(N+K)$가 된다.

아래는 AC코드다. 시작 위치는 tail로 표현했고 사이클 길이는 cyclc로 표현했다. $b_i$를 받을 때 long long을 사용해야되는 것과 사이클 길이가 0일 때를 조심해야 한다.

#include<bits/stdc++.h>
#define MAX 500000
using namespace std;
// deteministic sequence modulo K has cycle, and it forms like rho(greek alphabet)
int ten_tail, ten_cycle, one_tail, one_cycle;
int N,K;
int ten_idx[MAX], one_idx[MAX], ten_val[MAX], one_val[MAX];
// ten_val[i] = 10^i, one_val[i] = 1...1 with length i+1
int val;
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> K;
    memset(ten_idx, -1, sizeof(ten_idx));
    ten_tail = 0;
    val = 1;
    while(1) {
        if(ten_idx[val] != -1) {
            ten_cycle = ten_tail - ten_idx[val];
            ten_tail -= ten_cycle;
            break;
        }
        ten_idx[val] = ten_tail;
        ten_val[ten_tail++] = val;
        val = (val * 10) % K;
    }
    memset(one_idx, -1, sizeof(one_idx));
    one_tail = 1;
    val = 1;
    while(1) {
        if(one_idx[val] != -1) {
            one_cycle = one_tail - one_idx[val];
            one_tail -= one_cycle;
            break;
        }
        one_idx[val] = one_tail;
        one_val[one_tail++] = val;
        val = (val*10 + 1) % K;
    }
    int ans = 0;
    for(int i=0;i<N;++i) {
        long long a,b;
        cin >> a >> b;
        int ten, one;
        ten = b <= ten_tail? ten_val[b] : ten_cycle? ten_val[(b-ten_tail)%ten_cycle+ten_tail] : ten_val[ten_tail];
        one = b <= one_tail? one_val[b] : one_cycle? one_val[(b-one_tail)%one_cycle+one_tail] : one_val[one_tail];
        one = (one * a) % K;
        ans = (1LL * ans * ten) % K;
        ans = (ans + one) % K;
    }
    cout << ans << '\n';
    return 0;
}