안녕하세요,
재재입니다.
BOJ 14441 사이클의 개수 문제 풀이입니다.
BOJ 14441 사이클의 개수
(1) 문제 설명
분류 : math
출처 : https://www.acmicpc.net/problem/14441
관련 : https://www.acmicpc.net/problem/12850
방향 그래프가 주어지고,
길이가 (1,000,000) K보다 작은 서로 다른 사이클의 개수를 찾아주면 됩니다.
그래프 노드의 개수 (35이하) N, (1,000,000,000이하) M으로 나눈 나머지가 주어집니다.
이때, 같은 노드가 여러번 등장해도 상관 없습니다.
(2) 풀이 도출
이 문제의 관련 문제로, 본대 산책2 문제가 있습니다.
요약하면,
K가 주어지고 정확하게 K번만에 해당 위치로 돌아오는 경우의 수를 구하는 문제로
일단, 정보를 행렬로 표현 할 수 있습니다.
행렬 A의 각 원소 $$ a_{ij} $$ 는
i번 노드에서 출발해서 1번만에 j번 노드로 오는 경우의 수로 정의하면,
$$ B = A^2 $$ 이라고 했을 때,
원소 $$ b_{ij} $$ 는 i번 노드에서 출발해서 2번만에 j번 노드로 오는 경우의 수가 됩니다.
이제 $$ A^K $$ 를 구하면 K번만에 i번 노드에서 j로 오는 경우의 수를 구할 수 있습니다.
이 문제에서 요구하는 정답은
$$ A + A^2 + A^3 + … + A^K $$ 와 같습니다.
일단, \( A^K \) 를 빠르게 계산하기 위해서는 $$ A, A^2, A^4, A^8, … $$ 을 계산하면 됩니다.
$$ A + A^2 + A^3 + … + A^K $$ 를 빠르게 계산하기 위해서는
$$ (E+A)(E+A^2)(E+A^4) = E + A + A^2 + A^3 + A^4 + A^5 + A^6 + A^7 $$ 을 참고하시면 되겠습니다.