글 읽기 - 반례 부탁드립니다.

dmswl022329 2년 전 0

예제입력은 잘 나오는데 어떤부분이 틀렸는지 잘 모르겠습니다.

#include<bits/stdc++.h>
#define mod 1000
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> matrix;


ll N, K;


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

// 행렬 a * b
matrix operator * (const matrix &a, const matrix &b){
	ll size = a.size();
	matrix res(size,vector<ll>(size));
	for(ll i = 0; i < size; i++){
		for(ll j = 0; j < size; j++){
			for(ll 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, ll n){
	ll size = a.size();
	matrix res = matrix(size, vector<ll>(size));
	for(ll 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){
	ll size = a.size();
    for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            cout << a[i][j] << " ";
        }
        cout << '\n';
    }
}

ll mul(ll A, ll B){
	if(B == 1) return A;
	if(B % 2 == 0) return mul((A * 2) % mod, (B / 2)) % mod;
	else return (mul(A, B - 1) + A) % mod;
}

void initA(matrix &a){
	ll size = a.size();
	for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
    		cin >> a[i][j];
        }
    }
}

matrix sol(matrix a, ll last){
	ll size = a.size();
	matrix E(size, vector<ll>(size));
	for(int i = 0; i < size; i++) E[i][i] = 1; // 단위행렬 E
	if(last == 1) return a; // 마지막 항의 지수가 1이면 a^1 을 반환
	if(last % 2 == 0) return sol(a, last / 2) * (power(a, last / 2) + E); // 마지막 항의 지수가 짝수면 두개로 나눔
	else return sol(a, last - 1) + power(a, last); //  마지막 항의 지수가 홀수면 끝부분만 따로 더함.
}

int main() {
	ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
	cin >> N >> K;
	matrix A(N, vector<ll>(N));
	initA(A); // A 입력 받기
	printmatrix(sol(A, K)); // A^1 + ... + A^K 까지 구해서 출력하기 
	return 0;
}

hojoon0205 2년 전 3

입력의 제한 범위를 아주 잘 읽어보세요

dmswl022329 2년 전 2

이건.... 뭐 ㅋㅋㅋㅋㅋㅋㅋ

솔직히 B가 1일때 반례겠거니 했는데

이런걸줄은 ㅋㅋㅋㅋ

감사합니다.

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

문제

문제

출처

ICPC

반례 부탁드립니다.

dmswl022329 2년 전 0

hojoon0205 2년 전 3

dmswl022329 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말