글 읽기 - 다른방식으로 풀어봤는데 반례좀 부탁드려요

dmswl022329 2년 전 1

를 보고 코드를 짜봤는데

사이트에서 말하는 알고리즘을 따라했는데

케이스를 만들기도 검증하기도 쉽지 않네요...

어디가 문제일까요?

#include<bits/stdc++.h>
#define mod 1000003
using namespace std;
typedef vector<vector<int>> matrix;

int N, S, E, T;

matrix operator * (const matrix &a, const matrix &b){
	int size = a.size();
	matrix res(size,vector<int>(size));
	for(int i = 0; i < size; i++){
		for(int j = 0; j < size; j++){
			for(int k = 0; k < size; k++){
					res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod;
			}
		}
	}
	return res;
}


// 행렬 a의 n 제곱
matrix power(matrix a, int n){
	int size = a.size();
	matrix res = matrix(size, vector<int>(size));
	for(int i = 0; i < size; i++) res[i][i] = 1;
	while(n > 0){
		if(n % 2 == 1) res = res * a;
		n /= 2;
		a = a * a;
	}
	return res;
}

void printmatrix(const matrix &a){
	int size = a.size();
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            cout << a[i][j] << " ";
        }
        cout << '\n';
    }
}
// 입력을 행렬로 만드는 함수
void initA(matrix &a){
	int size = a.size();
	for (int i = 0; i < N; i++) {
    	string path;
    	cin >> path;
        for (int j = 0; j < N; j++) {
        	if((int)(path[j] - '0') >= 1){
		    	a[i * 5][j * 5 + (int)(path[j] - '0') - 1] = 1;
        	}
        	for(int j = 0; j < 4; j++){
        		a[i * 5 + j + 1][i * 5 + j] = 1;
        	}
        }
    }
}


int main() {
	ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
	cin >> N >> S >> E >> T;
	matrix A(N * 5, vector<int>(N * 5));
	initA(A);
	cout << power(A, T)[(S - 1) * 5][(E - 1) * 5] % mod;
	return 0;
}

/*
input	:	012
			201
			120
			
		0-1	0-2	0-3	0-4	0-5	|	1-1	1-2	1-3	1-4	1-5	|	2-1	2-2	2-3	2-4	2-5
		0	1	2	3	4	|	5	6	7	8	9	|	10	11	12	13	14
0-1	0	0	0	0	0	0	|	1	0	0	0	0	|	0	1	0	0	0
0-2	1	1	0	0	0	0	|	0	0	0	0	0	|	0	0	0	0	0
0-3	2	0	1	0	0	0	|	0	0	0	0	0	|	0	0	0	0	0
0-4	3	0	0	1	0	0	|	0	0	0	0	0	|	0	0	0	0	0
0-5	4	0	0	0	1	0	|	0	0	0	0	0	|	0	0	0	0	0
---------------------------------------------------------------------------
1-1	5	0	1	0	0	0	|	0	0	0	0	0	|	1	0	0	0	0
1-2	6	0	0	0	0	0	|	1	0	0	0	0	|	0	0	0	0	0
1-3	7	0	0	0	0	0	|	0	1	0	0	0	|	0	0	0	0	0
1-4	8	0	0	0	0	0	|	0	0	1	0	0	|	0	0	0	0	0
1-5	9	0	0	0	0	0	|	0	0	0	1	0	|	0	0	0	0	0
---------------------------------------------------------------------------
2-1	10	1	0	0	0	0	|	0	1	0	0	0	|	0	0	0	0	0
2-2	11	0	0	0	0	0	|	0	0	0	0	0	|	1	0	0	0	0
2-3	12	0	0	0	0	0	|	0	0	0	0	0	|	0	1	0	0	0
2-4	13	0	0	0	0	0	|	0	0	0	0	0	|	0	0	1	0	0
2-5	14	0	0	0	0	0	|	0	0	0	0	0	|	0	0	0	1	0


000001000001000
100000000000000
010000000000000
001000000000000
000100000000000
010000000010000
000001000000000
000000100000000
000000010000000
000000001000000
100000100000000
000000000010000
000000000001000
000000000000100
000000000000010

*/

dmswl022329 2년 전 0

언제나 주의해야할 오버플로우

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

문제

문제

출처

ICPC

다른방식으로 풀어봤는데 반례좀 부탁드려요

dmswl022329 2년 전 1

dmswl022329 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말