Binary Lifting

 

 

 

 

 

 

 

 

테이블 쌓는 순서 매우 중요 , ac 와 wa 사이의 결과 차이가 남

 

// 위에 next[i] 관련은 생략됨

for (int j=1; j<=31; j++)
{
    for (int i=1; i<=N; i++)
        jump[i][j] = jump[jump[i][j-1]][j-1];
}

int current_point = 1;

for (int i=0; i<=31; i++)
{
    if ( ( (K>>i) & 1 ) == 1 )
        current_point = jump[current_point][i];
}