[백준]본대 산책2(12850)

문제 링크 : [백준]본대 산책2(12850)

문제 설명

그래프가 주어져있고, 1번 노드에서 출발하여, N번 이동해서 1번 노드로 돌아오는 경우의 수를 구하세요.

입력

N(이동횟수, 1 <= N <= 1,000,000,000)

100000000

출력

261245548

카테고리

#DP #그래프 #분할정복

시간 복잡도 상한

노드 수가 8로 매우 작으나, N이 매우 커, N이 logN까지 줄여야 할 것 같습니다.

해결 방법

1. N이 작다면, 그래프 순회를 하여 구할 수 있습니다.
2. N이 매우 커, N번 순회를 시키기만 하더라도 타임아웃이 됩니다.
3. 그래프를 인접행렬로 나타내게 되면, 1번의 이동으로 갈 수 있는 노드 관계들이 파악됩니다.
4. 그 인접행렬을 제곱하게 된다면, 2번의 이동으로 갈 수 있는 경우의 수들이 파악됩니다.
5. 즉, K제곱을 하게되면 K번의 이동으로 갈 수 있는 경우의 수들이 파악됩니다.
6. 그러나 마찬가지로 N제곱을 하게되면 바로 타임아웃이 됩니다.
7. X^N = X^N/2 * X^N/2의 관계를 이용합니다.
   7-1. N이 홀수인 경우는 N/2를 계산한 다음 행렬을 한번 더 곱합니다.
8. N제곱을 반씩 쪼개 계산하면서 logN번만에 계산을 완료합니다.

시간복잡도

O(8³ * logN)

코드

#include<cstdio>
#include<string.h>
int n,i,j,k;
struct D{
    D(){memset(d,0,sizeof(d));}
    long long d[8][8];
};
D x;
D r(int n){
    if(n==1)return x;
    D q=r(n>>1);
    D ret;
    for(int i=0;i<8;i++)for(int j=0;j<8;j++)for(int k=0;k<8;k++)ret.d[i][j]=(ret.d[i][j]+q.d[i][k]*q.d[k][j])%1000000007;
    if(n&1){
        D w;
        for(int i=0;i<8;i++)for(int j=0;j<8;j++)for(int k=0;k<8;k++)w.d[i][j]=(w.d[i][j]+ret.d[i][k]*x.d[k][j])%1000000007;
        return w;
    }else return ret;
}
int main(){
    x.d[0][1]=x.d[0][2]=x.d[1][0]=x.d[1][2]=x.d[1][3]=x.d[2][0]=x.d[2][1]=x.d[2][3]=x.d[2][5]=x.d[3][1]=x.d[3][2]=x.d[3][4]=x.d[3][5]=x.d[4][3]=x.d[4][5]=x.d[4][6]=x.d[5][2]=x.d[5][3]=x.d[5][4]=x.d[5][7]=x.d[6][4]=x.d[6][7]=x.d[7][5]=x.d[7][6]=1;
    scanf("%d",&n);
    printf("%lld",r(n).d[0][0]);
}