글 읽기 - 시간복잡도가 O(m^3log(n)) 인데 통과가 안되는 이유?

swj0324 1년 전 1

n의 최대 입력값이 10^18 <= 2^60 이고, m의 최대 입력값이 100이면

분할 정복을 이용한 matrix_pow에서 mul 이 호출될 수 있는 최대 횟수는

대략 n이 이진수로 11......11인 경우 120번 정도이고

mul 한번 호출당 100^3 = 10^6 이니까

120 * 백만 = 1.2억 이니

제한 시간 3초안에 돌아가야 하는것 아닌가요?

제가 뭘 간과 했을까요...?

#include <iostream>
#include <vector>

#define MAX_SIZE 100

using namespace std;

long long int mod = 1000000007ll;
long long int n, m;

vector<vector<long long int>> mul(vector<vector<long long int>> m1, vector<vector<long long int>> m2){
	vector<vector<long long int>> ret(m, vector<long long int>(m));
	for(int i=0; i<m; i++){
		for(int j=0; j<m; j++){
			long long int sum = 0;
			for(int k=0; k<m; k++){
				long long int cal = ((m1[i][k] % mod) * (m2[k][j] % mod)) % mod;
                sum = ((sum%mod)+(cal%mod))%mod;
			}
			ret[i][j] = sum;
		}
	}
	return ret;
}

vector<vector<long long int>> matrix_pow(vector<vector<long long int>> m1, long long int pow){
	if(pow==0){
		vector<vector<long long int>> I(m, vector<long long int>(m, 0));
		for(int i=0; i<m; i++){
			I[i][i] = 1;
		}
		return I;
	}
	if(pow%2){ // 홀수승
		return mul(matrix_pow(m1, pow-1), m1);
	}
	else{ // 짝수승
		vector<vector<long long int>> half = matrix_pow(m1, pow/2);
		return mul(half, half);
	}
}

int main(){
	
	cin >> n >> m;

	//init 행렬 초기화
	vector<vector<long long int>> init(m, vector<long long int>(m,0));
	
	for(int c=0; c<m; c++){
		init[0][c] = 1;
	}
	
	//R 행렬 초기화
	vector<vector<long long int>> R(m, vector<long long int>(m,0));
	
	R[0][0] = 1;
	R[m-1][0] = 1;
	
	for(int c=1; c<m; c++){
		R[c-1][c] = 1;
	}
	
	if(n<m){
		cout << 1 << "\n";
	}
	else{
		vector<vector<long long int>> cnt = mul(init, matrix_pow(R, n-m+1));
		cout << cnt[0][0] << "\n";
	}

}

이유는 나누기 연산은 프로세서가 처리하는 모든 연산 중 가장 느린 것에 속하기 때문입니다. mod가 const가 아닌 경우, 컴파일러는 그 느린 나누기 명령을 그대로 수행하도록 코드를 만들 수밖에 없습니다. 하지만 const로 선언된 경우, 컴파일러는 나누기 명령을 만들어내는 대신 같은 결과를 내는 다른 연산(비트 연산이나 덧셈, 곱셈 등)들을 조합하여 훨씬 빠르게 연산을 수행하도록 만들 수 있게 됩니다.

djm03178 1년 전 1

또한 코드 자체에 모듈로 연산이 불필요하게 많습니다. 18번째 줄의 마지막에 있는 %를 제외하고는 모두 지워도 됩니다. 그러면 나누기 연산의 수를 1/6로 줄일 수 있게 됩니다.

swj0324 1년 전 0

mod를 const로 선언하니까 통과가 안되던게

600ms 만에 돌아가고

불필요한 모듈로 연산을 줄이니까

450ms 정도로 실행속도가 단축이 되네요.

이거 때문에 어제부터 많이 답답했는데 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간복잡도가 O(m^3log(n)) 인데 통과가 안되는 이유?

swj0324 1년 전 1

djm03178 1년 전 1

djm03178 1년 전 1

swj0324 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말