글 읽기 - 틀린 이유를 못찾겠습니다

hyunynim 5년 전 1

시간안에 문제를 해결하기 위해 행렬 곱셈을 이용하여 문제를 해결하였는데요

같은 코드로 나머지 연산만 없애고 2133 타일 채우기 문제에서는 AC를 받았지만 이문제는 WA가 나옵니다.

조언좀 해주시면 감사하겠습니다.

hyunynim 5년 전 3

음수와 뺄셈의 모듈러 연산을 고려를 안해서 틀렸습니다. 해결했습니다

yoodly 5년 전 3

귀중한 조언 덕분에 맞힐 수가 있었습니다. 감사합니다~

참고 자료 : http://ksj14.tistory.com/entry...

dlftls38 4년 전 0

감사합니다 저도 덕분에 맞았습니다!

하지만 참고 자료도 읽어보았지만 이유는 잘 모르겠습니다.

혹시 이유 좀 설명 해주실 수 있나요??

제 생각의 한계로는 우선 행렬의 인자가 음수여야하는건데 N이 커져서 음수인 값의 절댓값이 MOD보다 커져서 %MOD하는건데

그 음수인 값의 절댓값이 MOD보다는 작을 때도 그 음수 값에 MOD를 더한 후 %MOD하면 양수가 되어버리는데 왜 이것이 성립하는 것인가요?

예를 들어 -4가 있고 MOD가 7이면 원래 -4 % 7 은 -4인데 (-4 + 7)%7을 해버리면 3이됩니다.

이해를 못하겠습니다 ㅠㅠ

코드는 AC받은 행렬곱셈 함수 부분입니다.

12번째 줄을 말하는 것인데!! 부탁드립니다!!

vector<vector<long long>> matrix_mul(vector<vector<long long>>& a, vector<vector<long long>>& b){
	int i,j,k;
	int n = a.size();
	vector<vector<long long>> c(n, vector<long long>(n));
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			for (k = 0; k < n; k++)
			{
				c[i][k] += a[i][j] * b[j][k];
				c[i][k] = (c[i][k] + MOD)%MOD; // c[i][k]가 음수이고 절댓값이 MOD보다 작을때 (c[i][k] + MOD)%MOD는 양수가 되니 문제가 생겨야 하지 않나요?
			}
		}
	}
	return c;
}

yousrain 3년 전 0

오래된 글이지만 모듈러 때문에 2시간 정도 고통 받고 작성한 제 코드 올려요!

약간 무식하긴 한데 곱셈 시 일단 MOD만큼 무조건 더해서 음수가 아님을 보장하고

결과값을 더한 뒤

마지막에 다시 모드를 취했습니다!

void mat(ll a[2][2], ll b[2][2], ll c[2][2]){
	for(int i = 0; i < 2 ; i++)
		for(int j = 0; j < 2; j++)
			c[i][j] = MOD;
	c[0][0] += ((a[0][0]*b[0][0])%MOD+(a[0][1]*b[1][0])%MOD)%MOD;
	c[0][1] += ((a[0][0]*b[0][1])%MOD+(a[0][1]*b[1][1])%MOD)%MOD;
	c[1][0] += ((a[1][0]*b[0][0])%MOD+(a[1][1]*b[1][0])%MOD)%MOD;
	c[1][1] += ((a[1][0]*b[0][1])%MOD+(a[1][1]*b[1][1])%MOD)%MOD;
	c[0][0] %= MOD;
	c[0][1] %= MOD;
	c[1][0] %= MOD;
	c[1][1] %= MOD;
}

ksj14 1년 전 0

👍

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

문제

문제

출처

ICPC

틀린 이유를 못찾겠습니다

hyunynim 5년 전 1

hyunynim 5년 전 3

yoodly 5년 전 3

dlftls38 4년 전 0

yousrain 3년 전 0

ksj14 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말