글 읽기 - 9341번 ZZ 질문입니다

thdtjdals3 3년 전 0

01000...0000

11000...0000

11100...0000

11110...0000

...

11111...1111

위와 같이 생긴 (c+2) x (c+2) 정사각행렬 Base를 (d-1)승하여 구하는 방법으로 풀어보려했습니다.

이 방법 자체는 이전 질문글을 확인해보니까 올바른 방법같은데, 제 코드에서 어떤 방법으로 시간초과를 해결할 수 있을 지 모르겠습니다.

어떻게 하면 좋을까요??

#include <stdio.h>
#define modulo 1000000009

typedef struct {
	long long array[102][102];
} Matrix;

Matrix matrix_multiply_modular (Matrix A, Matrix B, int N, long long M);
Matrix matrix_power_modular (Matrix A, int N, long long K, long long M);

int main() {
	
	int T;
	scanf("%d", &T);
	while(T--) {
		
		long long a, b, c, d;
		scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
		
		int i, j;
		
		Matrix Base;
		for (i = 0; i < c + 2; i++) {
			for (j = 0; j < c + 2; j++) {
				if (i == 0) {
					if (j == 1) {
						Base.array[i][j] = 1;
					}
					else {
						Base.array[i][j] = 0;
					}
				}
				else {
					if (j <= i) {
						Base.array[i][j] = 1;
					}
					else {
						Base.array[i][j] = 0;
					}
				}
			}
		}
		Base = matrix_power_modular(Base, c+2, d-1, modulo);
		
		long long answer = (Base.array[c+1][0] * (b - a)) % modulo;
		answer = (answer + modulo) % modulo;
        
		for (i = 1; i < c + 2; i++) {
			answer += a * Base.array[c+1][i];
			answer %= modulo;
		}
        
		printf("%lld\n", answer);
	}
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int N, long long M) {
	Matrix result;
	int i, j, k;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			result.array[i][j] = 0;
			for (k = 0; k < N; k++) {
				long long temp = (A.array[i][k] * B.array[k][j]) % M;
				result.array[i][j] = (result.array[i][j] + temp) % M;
			}
		}
	}
	return result;
}

Matrix matrix_power_modular (Matrix A, int N, long long K, long long M) {
	Matrix result;
	int i, j;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (i == j) {
				result.array[i][j] = 1;
			}
			else {
				result.array[i][j] = 0;
			}
		}
	}
	while (K > 0) {
		if (K & 1) {
			result = matrix_multiply_modular(result, A, N, M);
		}
		A = matrix_multiply_modular(A, A, N, M);
		K >>= 1;
	}
	return result;
}

thdtjdals3 3년 전 0

비트연산자를 버리고, Matrix 구조체에 있던 array를 unsigned long long으로 해주고, 45~51줄을 그냥 행렬곱으로 처리했습니다.

Base 관련해서 코드를 조금이나마 더 간결하게 바꿨어요. 결과적으로 5288ms로 통과했습니다.

//수정된 Base코드, size = c + 2
Matrix Base;
for (int i = 0; i < size; i++) {
	for (int j = 0; j < size; j++) {
		if (j <= i) {
			Base.array[i][j] = 1;
		}
		else {
			Base.array[i][j] = 0;
		}
	}
}
Base.array[0][0] = 0, Base.array[0][1] = 1;

thdtjdals3 3년 전 0

그런데 이번에는 호기심으로 unsigned long long(26364485)을 long long(26364928)으로 써봤는데 오히려 메모리 사용량도 4KB 늘고 시간도 1000ms는 증가하네요;;

이 이유는 진짜 모르겠습니다 ㅜㅜ

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

문제

문제

출처

ICPC

9341번 ZZ 질문입니다

thdtjdals3 3년 전 0

thdtjdals3 3년 전 0

thdtjdals3 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말