글 읽기 - 반례가 뭐가 있을까요...

qkrlwsnd 4년 전 0

진짜 왜틀렸는지 모르겠네요 ㅜㅜ

2 1

1000 1000

1000 1000도 통과하는데..

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef vector<vector<long long> > MATRIX;
MATRIX mat_multiple(MATRIX a, MATRIX b);
MATRIX calcul(MATRIX a, int n)
{
	if (n == 1) 
    {
        for (int i = 0; i < a.size(); i++)
            for (int j = 0 ; j < a.size(); j++)
                a[i][j] %= 1000;
        return a;
    }
	else if (n % 2)
	{
		MATRIX half = calcul(a, (n - 1) / 2);
		return mat_multiple(mat_multiple(a, half), half);
	}
	else
	{
		MATRIX half = calcul(a, n / 2);
		return mat_multiple(half, half);
	}
}
MATRIX mat_multiple(MATRIX a, MATRIX b)
{
	MATRIX c;
	c.resize(a.size());
	for (int i = 0; i < a.size(); i++)
		c[i].resize(a.size());
	memset(&c, sizeof(c), 0);
	for (int i = 0; i < a.size(); i++)
		for (int j = 0; j < a.size(); j++)
        {
			for (int k = 0; k < a.size(); k++)
			{
				c[i][j] += ((a[i][k] % 1000) * (b[k][j] % 1000)) % 1000;
				c[i][j] %= 1000;
			}
            c[i][j] %= 1000;
        }
	return c;
}
int main()
{
	long long N, B; MATRIX v;
	cin >> N >> B;
	v.resize(N);
	for (int i = 0; i < N; i++)
		v[i].resize(N);
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> v[i][j];
	v = calcul(v, B);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			printf("%lld ", v[i][j] % 1000);
		printf("\n");
	}
}

sait2000 4년 전 1

calcul의 두번째 인자가 int입니다. 주어지는 범위가 int 범위를 넘기 때문에 틀리게 됩니다.

qkrlwsnd 4년 전 0

와 ㅋㅋㅋ 저걸 왜 못봤지..

감사합니다

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

문제

문제

출처

ICPC

반례가 뭐가 있을까요...

qkrlwsnd 4년 전 0

sait2000 4년 전 1

qkrlwsnd 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말