글 읽기 - 왜 시간초과가 나는지 모르겠습니다.

ykmyou 7년 전 0

테스트 케이스는 정답이 다 나오는데

어느 부분에서 시간초과가 나는지 모르겠습니다.

부탁드립니다ㅠㅠㅠ

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef vector<vector<long long> > matrix;
long long N, M, A, B, C, T;

matrix unit(long long n) {
	matrix ret(n, vector<long long>(n));
	for (long long i = 0; i < n; i++)
		ret[i][i] = 1;
	return ret;
}
matrix matrixMul(const matrix &a, const matrix &b) {
	long long n = a.size();
	long long m = a[0].size();
	long long k = b[0].size();
	matrix ret(n, vector<long long>(k));
	for (long long i = 0; i < n; i++)
	for (long long j = 0; j < k; j++)
	for (long long p = 0; p < m; p++)
		ret[i][j] = (ret[i][j] + (long long)a[i][p] * b[p][j])%M;
	return ret;
}

matrix temp[65];
int main(){

	for (int i = 0; i < 65; i++){
		temp[i].resize(50);
		for (int j = 0; j < 50; j++){
			temp[i][j].resize(50);
			for (int k = 0; k < 50; k++)
				temp[i][j][k] = 0;
		}
	}
	matrix S(50, vector<long long>(1));
	while (scanf("%lld %lld %lld %lld %lld %lld", &N, &M, &A, &B, &C, &T)){
		if (N == 0 && M == 0 && A == 0 && B == 0 && C == 0 && T == 0)
			break;

		for (int i = 0; i < N; i++)
			scanf("%lld", &S[i][0]);
		
		for (int i = 0; i < N; i++){
			if (0 <= i - 1)
				temp[0][i][i - 1] = A;
			if (i + 1<N)
				temp[0][i][i + 1] = C;
			temp[0][i][i] = B;
		}
		for (int i = 1; i<65; i++)
			temp[i] = matrixMul(temp[i - 1], temp[i - 1]);
		
		matrix ans = unit(N);
		long long i = 0;
		while (T > 0){
			if (T & (1LL << i)){
				ans = matrixMul(ans, temp[i]);
				T -= (1LL << i);
			}
			i++;
		}
		
		long long R;
		for (int i = 0; i < N; i++){
			R = 0LL;
			for (int j = 0; j < N; j++)
				(R += (ans[i][j] * S[j][0]))%=M;
			printf("%lld ", R);
		}
		printf("\n");
	}
	return 0;
}

dmswl022329 2년 전 0

아래 코드는

모듈러 연산을 n * k * m 번 하게 됩니다.

모듈러 연산은 시간을 많이 먹는 연산이기때문에

필요할때만 하면 시간이 확 줄어들겁니다.

조건문으로 해야할때만 모듈러 연산을 하면 될거같습니다.

	for (long long i = 0; i < n; i++)
	for (long long j = 0; j < k; j++)
	for (long long p = 0; p < m; p++)
		ret[i][j] = (ret[i][j] + (long long)a[i][p] * b[p][j])%M;

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

문제

문제

출처

ICPC

왜 시간초과가 나는지 모르겠습니다.

ykmyou 7년 전 0

dmswl022329 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말