https://www.acmicpc.net/problem/10830
Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> calc(vector<vector<int>> aa, vector<vector<int>> bb)
{
int n = aa.size();
vector<vector<int>> res(n);
for (int i = 0; i < n; i++)
{
res[i].resize(n, 0);
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
res[i][j] += (aa[i][k] * bb[k][j]) % 1000;
}
res[i][j] %= 1000;
}
}
return res;
}
vector<vector<int>> func(vector<vector<int>> a, long long b)
{
if (b == 1)
{
return a;
}
vector<vector<int>> c = calc(func(a, b / 2), func(a, b / 2));
if (b % 2 == 1)
{
return calc(c, a);
}
else
{
return c;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
long long n, b;
cin >> n >> b;
vector<vector<int>> a(n);
for (int i = 0; i < n; i++)
{
a[i].resize(n, 0);
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> a[i][j];
}
}
vector<vector<int>> answer = func(a, b);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << answer[i][j] % 1000 << ' ';
}
cout << '\n';
}
return 0;
}
a^b에서 b가 큰 수일 때 연산 하는거 그대로 따라서
재귀로 풀었는데 시간초과나버림. 접근 방법이 잘못됐나요
ㅇㅇ 빠른거듭제곱 풀듯 푸는 문제임
시간초과가 계속 떠서 잘못 생각한건가 했어요.
잘못생각한거 맞단건데
제가잘못 이해했네요 죄송
알려주신 알고리즘 찾아서 풀었어요 고맙습니다.
님풀이 틀림 b가 2^36-1 이라고 생각해보셈 그러면 님 풀이는 행렬곱을 1 + 2 + 4 + ... 2^35 번 해야하니까 연산횟수대략 2^35*5^3번, 대략 80000초가 넘게걸림. 당연히 안돌아가는 풀이임
그렇군요 감사합니다!