백준 BOJ 12878번 : Blocks
문제 난이도 : Gold III
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
N개의 블럭을 각각 빨강, 주황, 노랑, 초록색 중 하나로 칠하는데 그들 중 빨간색으로 칠해진 블럭과 노란색으로 칠해진 블럭이 각각 짝수개인 경우의 수를 구하는 문제이다.
가장 간단한 해결책은 N = 5 정도까지 완전 탐색으로 모든 경우를 count 해본 뒤, 규칙을 찾아 일반항을 찾는 방법이 있다.
직접 계산하는 방법은 위와 같다.
빨간색 또는 노란색으로 칠할 블럭을 선택하고, 그들 중 빨간색으로 칠할 블럭을 고른다.
나머지 블럭 중에서는 초록색 또는 주황색 중 어떤 색으로 칠할지를 고른다.
이 문제의 식 유도에서 핵심은 NC0 + NC2 + NC4 + ... = 2^(N-1)임을 알고 있어야 한다는 것이다.
홀수인 경우에도 똑같이 2^(N-1)이니 까먹지 않도록 하자.
N이 최대 10^9이므로 O(N) 시간도 부족하다.
따라서 분할 정복을 이용한 거듭제곱을 이용하여 log 시간에 거듭제곱을 수행할 수 있도록 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
int mod = 1e4 + 7;
int a = 1, ba = 2, ex = N-1;
while(ex > 0) {
if(ex % 2 == 1) a = (a * ba) % mod;
ba = (ba * ba) % mod;
ex /= 2;
}
int b = 1; ba = 2, ex = 2*(N-1);
while(ex > 0) {
if(ex % 2 == 1) b = (b * ba) % mod;
ba = (ba * ba) % mod;
ex /= 2;
}
int ans = (a + b) % mod;
cout << ans << "\n";
}
백준 BOJ 11693번 : n^m의 약수의 합
문제 난이도 : Gold II
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
n^m의 모든 약수의 합 mod (1e9 + 7)의 값을 구하는 문제이다.
간단히 식 개형만 정리해보면 위와 같이 약수의 합을 (1 + p + p^2 + ... + p^kM) x (1 + q + q^2 + ... ) x ... 이런 식으로 나타낼 수 있다.
이 때 p^k는 N을 소인수분해 했을 때 나타나는 p의 최고 지수이다.
이 문제에서는 N을 M 제곱했기 때문에 최고 차항은 kM이 된다.
위의 항들을 일일이 더하면 결국 O(kM) 이상의 시간이 걸리므로 시간 초과가 발생한다.
따라서 이를 빨리 구해주기 위해 위에서 정리한 등비수열의 합 공식을 사용해준다.
분모의 경우에는 모듈로 역원 공식을 사용해서 풀어주면 된다. (a^(-1) ≡ a^(p - 2) (mod p))
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v;
int tmp = N;
for(int i=2; i*i<=tmp; i++) {
while(tmp % i == 0) {
v.push_back(i);
tmp /= i;
}
}
if(tmp > 1) v.push_back(tmp);
int cnt = 1, ans = 1, mod = 1e9 + 7;
for(int i=1; i<v.size(); i++) {
if(v[i] == v[i-1]) cnt++;
else {
int mul = 1, ba = v[i-1], ex = cnt*M + 1;
while(ex > 0) {
if(ex % 2 == 1) mul = (mul * ba) % mod;
ba = (ba * ba) % mod;
ex /= 2;
}
mul--;
ba = v[i-1] - 1, ex = mod - 2;
while(ex > 0) {
if(ex % 2 == 1) mul = (mul * ba) % mod;
ba = (ba * ba) % mod;
ex /= 2;
}
ans = (ans * mul) % mod;
cnt = 1;
}
}
if(v.size() > 0) {
int mul = 1, ba = v[v.size()-1], ex = cnt*M + 1;
while(ex > 0) {
if(ex % 2 == 1) mul = (mul * ba) % mod;
ba = (ba * ba) % mod;
ex /= 2;
}
mul--;
ba = v[v.size()-1] - 1, ex = mod - 2;
while(ex > 0) {
if(ex % 2 == 1) mul = (mul * ba) % mod;
ba = (ba * ba) % mod;
ex /= 2;
}
ans = (ans * mul) % mod;
}
cout << ans << "\n";
}
백준 BOJ 7677번 : Fibonacci
문제 난이도 : Gold II
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
피보나치 수에 대한 일반화 된 행렬 식을 주고, F_n을 구하게 하는 문제이다.
문제에서 행렬과 일반항에 대한 식을 모두 주었기 때문에 단순히 행렬을 N 제곱하여 F_N에 해당하는 원소의 값을 출력해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int>> mat;
int mod = 1e4;
mat f(mat& v, mat& u) {
int N = 2;
mat w(N, vector<int>(N));
for(int i=0; i<v.size(); i++)
for(int j=0; j<u[0].size(); j++)
for(int k=0; k<v[0].size(); k++)
w[i][j] = (w[i][j] + v[i][k] * u[k][j]) % mod;
return w;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
int N; cin >> N;
if(N == -1) break;
mat mul(2, vector<int>(2));
for(int i=0; i<2; i++) mul[i][i] = 1;
mat ba(2, vector<int>(2));
ba = {{1, 1}, {1, 0}};
while(N > 0) {
if(N % 2 == 1) mul = f(mul, ba);
ba = f(ba, ba);
N /= 2;
}
cout << mul[0][1] << "\n";
}
}
백준 BOJ 11442번 : 홀수번째 피보나치 수의 합
문제 난이도 : Gold II
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
문제 이름 그대로 홀수번째 피보나치 수의 합을 구하는 문제이다.
이 때 F_0 = 0, F_1 = 1이며, 합을 1e9 + 7로 나눈 수를 답으로 제출해야 한다.
엄밀하게는 점화식이나 일반항을 찾아도 좋지만, 굳이 엄밀하게 풀 것이 아니라면 규칙성을 찾아서 풀어도 된다.
5줄까지만 적어보면 위와 같이 f(2k + 1) = f(2k) = F_2k임을 알 수 있다. (F_2k는 2k번째 피보나치 수)
따라서 2k번째 피보나치 수만 행렬과 빠른 거듭제곱을 활용하여 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int>> mat;
int mod = 1e9 + 7;
mat f(mat& v, mat& u) {
int N = 2;
mat w(N, vector<int>(N));
for(int i=0; i<v.size(); i++)
for(int j=0; j<u[0].size(); j++)
for(int k=0; k<v[0].size(); k++)
w[i][j] = (w[i][j] + v[i][k] * u[k][j]) % mod;
return w;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
if(N % 2 == 1) N++;
mat mul(2, vector<int>(2));
for(int i=0; i<2; i++) mul[i][i] = 1;
mat ba(2, vector<int>(2));
ba = {{1, 1}, {1, 0}};
while(N > 0) {
if(N % 2 == 1) mul = f(mul, ba);
ba = f(ba, ba);
N /= 2;
}
cout << mul[0][1] << "\n";
}
백준 BOJ 11443번 : 짝수번째 피보나치 수의 합
문제 난이도 : Gold II
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
이 문제 역시 위의 문제와 세트 문제로, 짝수번째 피보나치 수의 합을 구해 그것을 1e9 + 7로 나눈 나머지를 구하는 문제이다.
위와 같이 앞의 몇 항을 적어보면, N이 짝수일 때는 1 더해준 뒤 F_N - 1을 답으로 얻어주면 됨을 알 수 있다.
피보나치 수의 일반항을 구하는 과정은 위의 문제와 동일하다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int>> mat;
int mod = 1e9 + 7;
mat f(mat& v, mat& u) {
int N = 2;
mat w(N, vector<int>(N));
for(int i=0; i<v.size(); i++)
for(int j=0; j<u[0].size(); j++)
for(int k=0; k<v[0].size(); k++)
w[i][j] = (w[i][j] + v[i][k] * u[k][j]) % mod;
return w;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
if(N % 2 == 0) N++;
mat mul(2, vector<int>(2));
for(int i=0; i<2; i++) mul[i][i] = 1;
mat ba(2, vector<int>(2));
ba = {{1, 1}, {1, 0}};
while(N > 0) {
if(N % 2 == 1) mul = f(mul, ba);
ba = f(ba, ba);
N /= 2;
}
cout << mul[0][1] - 1 << "\n";
}
백준 BOJ 15999번 : 뒤집기
문제 난이도 : Gold III
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
B 또는 W로 이루어진 N x M의 배열에서 일부 칸을 뒤집어 인접한 같은 칸들이 모두 뒤집힌다고 할 때, 원래 배열로 가능했을 것의 경우의 수를 구하는 문제이다.
뒤집고 나서 옆에 다른 칸이 존재하는 것은 불가능하다.
따라서 상하좌우에 다른 칸이 존재하지 않는 칸은 선택했을 수도, 선택되지 않을 수도 있으므로 2^(상하좌우에 다른 칸이 존재하지 않는 칸)이 답이 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<char>> v(N, vector<char>(M));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) cin >> v[i][j];
int cnt = 0;
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) {
bool check = true;
int di[4] = {1, -1, 0, 0};
int dj[4] = {0, 0, 1, -1};
for(int k=0; k<4; k++) {
int ni = i + di[k];
int nj = j + dj[k];
if(ni < 0 || nj < 0 || ni >= N || nj >= M) continue;
if(v[ni][nj] != v[i][j]) check = false;
}
if(check) cnt++;
}
int ans = 1, ba = 2, ex = cnt, mod = 1e9 + 7;
while(ex > 0) {
if(ex % 2 == 1) ans = (ans * ba) % mod;
ba = (ba * ba) % mod;
ex /= 2;
}
cout << ans << "\n";
}
백준 BOJ 13172번 : Σ
문제 난이도 : Gold IV
알고리즘 분류 : 페르마의 소정리, 분할 정복을 이용한 거듭제곱
N쌍의 주어진 a/b들에 대해서, a x b^(-1) mod (1e9 + 7)들의 합을 구하는 문제이다.
페르마의 소정리를 활용하여 기약 분수를 모듈로에 대해 연산하는 방법을 알려주는 가장 기초적인 문제이다.
문제에서 하라는대로 구현해주면 된다.
페르마의 소정리에 의하면 소수 p에 대해 a^(-1) mod p는 a^(p-2) mod p와 같다.
따라서, a/b mod p는 a x b^(p-2) mod p를 구하라는 것과 같고, b^(p-2)는 빠른 거듭제곱을 구현하여 풀이해줄 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
int ans = 0, mod = 1e9 + 7;
while(N--) {
int a, b; cin >> b >> a;
int mul = a, ba = b, ex = mod - 2;
while(ex > 0) {
if(ex % 2 == 1) mul = (mul * ba) % mod;
ba = (ba * ba) % mod;
ex /= 2;
}
ans = (ans + mul) % mod;
}
cout << ans << "\n";
}
백준 BOJ 14440번 : 정수 수열
문제 난이도 : Gold IV
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
수열의 a0와 a1이 주어지고, a_i = x a_(i-1) + y a_(i-2)일 때 a_N을 구하는 문제이다.
행렬을 위와 같이 잡아 행렬 [ [x y] [1 0] ]을 (N-1)제곱하여 일반항을 구해줄 수 있다.
주의할 점은 A_N의 뒤의 "두 자리"를 구하라고 하였으므로, 답이 한 자리거나 0인 경우 앞에 0 하나를 더 붙여서 출력해주어야 한다는 것이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int>> mat;
int mod = 100;
mat f(mat& v, mat& u) {
mat w(2, vector<int>(2));
for(int i=0; i<v.size(); i++)
for(int j=0; j<u[0].size(); j++)
for(int k=0; k<v[0].size(); k++)
w[i][j] = (w[i][j] + v[i][k] * u[k][j]) % mod;
return w;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int x, y, a0, a1, N; cin >> x >> y >> a0 >> a1 >> N;
if(N == 0) {
printf("%02d\n", x);
return 0;
}
else if(N == 1) {
printf("%02d\n", y);
return 0;
}
mat mul(2, vector<int>(2));
for(int i=0; i<2; i++) mul[i][i] = 1;
mat ba(2, vector<int>(2));
ba[0][0] = x, ba[0][1] = y, ba[1][0] = 1, ba[1][1] = 0;
N--;
while(N > 0) {
if(N % 2 == 1) mul = f(mul, ba);
ba = f(ba, ba);
N /= 2;
}
int ans = (mul[0][0] * a1 + mul[0][1] * a0) % mod;
printf("%02d\n", ans);
}
백준 BOJ 4233번 : 가짜소수
문제 난이도 : Gold IV
알고리즘 분류 : 에라토스테네스의 체, 분할 정복을 이용한 거듭제곱
어떤 수 p가 소수가 아니면서 a^p ≡ a (mod p)라면 p를 가짜소수라고 할 때, a와 p가 주어졌을 때 p가 가짜소수인지를 판별하는 문제이다.
다시 적어보자면 p가 가짜소수이려면, 1. 소수가 아니어야 하고 2. a^p ≡ a (mod p)이어야 한다.
1번 조건은 에라토스테네스의 체를 이용하여 sqrt(p) 까지의 소수에 대해서만 나누어지는지 확인해보면 된다.
2번은 분할 정복을 이용한 거듭제곱을 수행하여 O(log p) 시간에 제곱값을 구하고, 이것이 mod p에 대해 a인지 확인해보면 된다.
주의할 점은 가짜소수는 합성수라는 것이다. 조건을 잘 읽어보아야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int Max = 1e5;
vector<bool> p(Max, true);
p[1] = false;
for(int i=2; i*i<Max; i++)
for(int j=2; i*j<Max; j++) p[i*j] = false;
vector<int> v;
for(int i=2; i<Max; i++)
if(p[i]) v.push_back(i);
while(true) {
int N, a; cin >> N >> a;
if(N == 0 && a == 0) break;
bool check = true;
for(int i=0; i<v.size() && v[i]*v[i] <= N; i++) {
if(N % v[i] == 0) check = false;
}
if(check) {
cout << "no\n";
continue;
}
int mul = 1, bas = a, exp = N;
while(exp > 0) {
if(exp % 2 == 1) mul = (mul * bas) % N;
bas = (bas * bas) % N;
exp /= 2;
}
if(mul == a) cout << "yes\n";
else cout << "no\n";
}
}
백준 BOJ 5095번 : Matrix Powers
문제 난이도 : Gold IV
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
N x N 행렬을 M 제곱한 행렬을 구하는 문제이다.
단순히 분할 정복을 이용한 거듭제곱 알고리즘을 이용하여 그대로 풀이 가능하다.
다만 행렬의 곱을 구현하는 부분에서 헷갈릴 수 있는데, A 행렬과 B 행렬의 곱의 경우 A 행렬의 행의 수만큼 행이 생기고, B행렬의 열의 수만큼 열이 생기며, 각 원소는 A 행렬의 열의 수 = B 행렬의 행의 수만큼의 원소들을 곱해서 더해야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int>> mat;
int N, mod, M;
mat f(mat& v, mat& u) {
mat w(N, vector<int>(N));
for(int i=0; i<v.size(); i++)
for(int j=0; j<u[0].size(); j++)
for(int k=0; k<v[0].size(); k++)
w[i][j] = (w[i][j] + v[i][k] * u[k][j]) % mod;
return w;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
cin >> N >> mod >> M;
if(N == 0 && mod == 0 && M == 0) break;
mat mul(N, vector<int>(N));
for(int i=0; i<N; i++) mul[i][i] = 1;
mat bas(N, vector<int>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) cin >> bas[i][j];
while(M > 0) {
if(M % 2 == 1) mul = f(mul, bas);
bas = f(bas, bas);
M /= 2;
}
for(int i=0; i<mul.size(); i++) {
for(int j=0; j<mul[0].size(); j++) cout << mul[i][j] << " ";
cout << "\n";
}
cout << "\n";
}
}
백준 BOJ 15710번 : xor 게임
문제 난이도 : Gold V
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
a에서 시작하여 0 ~ 2^31 - 1의 수를 하나 골라 xor하는 과정을 N번 거쳐 b를 만드는 경우의 수를 구하는 문제이다.
중간에 나올 수 있는 수는 0 ~ 2^31 - 1 중 어떤 것이든 가능하다.
즉, 중간에 거치는 수 하나 당 2^31가지의 경우의 수가 발생한다.
연산을 N번 거쳐 b가 되었다는 것은 중간 수가 N-1가지라는 의미이므로, 답은 (2^31)^(N-1)이 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int a, b, N; cin >> a >> b >> N;
int ans = 1, mod = 1e9 + 7;
int x = 1;
for(int i=1; i<=31; i++) x = (x * 2) % mod;
N--;
while(N > 0) {
if(N % 2 == 1) ans = (ans * x) % mod;
x = (x * x) % mod;
N /= 2;
}
cout << ans << "\n";
}
백준 BOJ 15717번 : 떡파이어
문제 난이도 : Gold V
알고리즘 분류 : 분할 제곱을 이용한 거듭제곱
자연수 N을 자연수들로 분할하는 경우의 수를 묻는 문제이다.
예를 들어 N = 4인 경우 3 = 2 + 1 = 1 + 2 = 1 + 1 + 1로 4가지이다.
N개의 공이 있고 그 사이에 막대로 분리하는 경우를 생각해보자.
N-1개의 사이 공간에 막대를 각각 놓을지 안 놓을지 2가지의 선택지가 있으므로 답은 2^(N-1)이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
N--;
int ans = 1, x = 2, mod = 1e9 + 7;
while(N > 0) {
if(N % 2 == 1) ans = (ans * x) % mod;
x = (x * x) % mod;
N /= 2;
}
cout << ans << "\n";
}
백준 BOJ 18291번 : 비요뜨의 징검다리 건너기
문제 난이도 : Gold V
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
1번 다리에서 N번 다리로 건너는데, 1번과 N번 사이에 있는 다리는 건너도 되고 안 건너도 될 때, 다리를 건너는 방법의 수를 구하는 문제이다.
선택이 가능한 다리는 N-2개이고 각각 건널지 말지를 선택할 수 있으므로, 답은 2^(N-2)이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N; cin >> N;
if(N < 2) {
cout << 1 << "\n";
continue;
}
N -= 2;
int ans = 1, x = 2, mod = 1e9 + 7;
while(N > 0) {
if(N % 2 == 1) ans = (ans * x) % mod;
x = (x * x) % mod;
N /= 2;
}
cout << ans << "\n";
}
}
백준 BOJ 24930번 : Ordinary Ordinals
문제 난이도 : Silver I
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
N 이하의 원소를 규칙에 따라 집합으로 표현했을 때, 문자열의 길이를 구하는 문제이다.
수열의 규칙성 문제의 경우 점화식만 찾아주면 된다.
N+1일 때, N까지의 원소들을 모두 한 번 출력하되 기존의 괄호(2개의 문자열)가 사라진다.
그 다음 콤마가 하나 붙고, N+1에 해당하는 원소가 같은 길이로 나오는데 이번에는 괄호가 붙어있다.
그리고 전체를 감싸는 괄호가 2개 나와야 한다.
그러면 f(N+1) = 2 x f(N) + 1임을 알 수 있다.
f(0)에서 f(1)로 갈 때는 쉼표가 없으므로 예외 처리를 해준다.
위의 점화식에서 일반항의 규칙을 잘 찾아보면 f(N) = 2^(N-2) x 10 - 1임을 알 수 있고, 2^(N-2)는 로그 시간 제곱으로 구해줄 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, mod; cin >> N >> mod;
if(N == 0) {
cout << 2 % mod << "\n";
return 0;
}
else if(N == 1) {
cout << 4 % mod << "\n";
return 0;
}
int ans = 1, a = 2;
N -= 2;
while(N > 0) {
if(N % 2 == 1) ans = (ans * a) % mod;
a = (a * a) % mod;
N /= 2;
}
ans = (ans * 10 - 1) % mod;
cout << ans << "\n";
}
백준 BOJ 24159번 : フェルマー方程式 (Fermat)
문제 난이도 : Silver I
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
N과 M이 주어질 때, 0 ~ M-1 사이의 x, y, z에 대해 x^N + y^N ≡ z^N (mod M)인 (x, y, z)의 개수를 구하는 문제이다.
0 ~ M-1인 a에 대해 a^N의 값들을 모두 구해놓고, mod M 값이 i인 것들을 u[i]에 저장한다.
여기서 u[i]는 z^N, 즉 우변에 해당하는 값들이 될 것이다.
이제 좌변의 mod 값들에 따른 개수들을 계산하자.
이중 for문을 이용하여 v[i] + v[j] 값들을 고려해주되, 그냥 계산하면 시간 초과가 나기 때문에 반으로 나눠서 i < j인 경우에 대해서만 count 해주고 나머지는 2배해주면 된다. (물론 i = j인 경우는 따로 count 해주어야 한다.)
이제 좌변과 우변이 같은 경우의 수들을 모두 세어주면 되는데, 이것은 O(M) 시간에 수행 가능하다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int M, N; cin >> M >> N;
vector<int> v(M, 1), u(M);
for(int i=0; i<M; i++) {
int a = i, b = N;
while(b > 0) {
if(b % 2 == 1) v[i] = (v[i] * a) % M;
a = (a * a) % M;
b /= 2;
}
u[v[i]]++;
}
vector<int> w(M);
for(int i=0; i<M; i++)
for(int j=i+1; j<M; j++) w[(v[i] + v[j]) % M] += 2;
for(int i=0; i<M; i++) w[(v[i] + v[i]) % M]++;
int ans = 0;
for(int i=0; i<M; i++) ans += u[i] * w[i];
cout << ans << "\n";
}
백준 BOJ 14731번 : 謎紛芥索紀 (Large)
문제 난이도 : Silver II
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
다항식이 주어질 때 f'(2)의 값을 구하는 문제이다.
k x^b를 미분하면 kb x^(b-1)이 되므로, 나머지는 계산해주고 x^(b-1)을 분할 정복을 이용한 거듭제곱으로 log 시간에 계산해주면 된다.
이 때 x = 2이므로, 2를 거듭제곱 해준다.
의문인 점은 mul = k * b를 했을 때 모듈로 처리를 안하면 틀린다는 것인데, 어차피 ans = (ans + mul) % mod에서 모듈로 연산이 될텐데 어디에서 오버플로우가 났는지 잘 모르겠다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
int ans = 0, mod = 1e9 + 7;
while(N--) {
int k, a = 2, b; cin >> k >> b;
int mul = (k * b) % mod;
b--;
while(b > 0) {
if(b % 2 == 1) mul = (mul * a) % mod;
a = (a * a) % mod;
b /= 2;
}
ans = (ans + mul) % mod;
}
cout << ans << "\n";
}
백준 BOJ 21854번 : Monsters
문제 난이도 : Silver III
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
N개의 수에 대해, 2^(a_i)의 합을 구하는 문제이다.
각 수에 대해 2의 거듭 제곱의 값을 분할 정복을 이용한 거듭제곱으로 log 시간에 구해주면 된다.
총 시간 복잡도는 O(N log K)가 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
int ans = 0, mod = 1e9 + 7;
while(N--) {
int b; cin >> b;
int mul = 1, a = 2;
while(b > 0) {
if(b % 2 == 1) mul = (mul * a) % mod;
a = (a * a) % mod;
b /= 2;
}
ans = (ans + mul) % mod;
}
cout << ans << "\n";
}
백준 BOJ 11366번 : Tons of Orcs, no Fibbin'
문제 난이도 : Silver III
알고리즘 분류 : 수학
등차수열의 첫 두 항 a와 b가 주어질 때, c+2번째 항의 값을 구하는 문제이다.
수가 기하급수적으로 늘어나므로 굳이 DP를 사용할 필요도 없이 단순 반복으로 계산이 가능하다.
다만 a = 0, b = 0일 경우 N을 아주 크게 주어도 답이 0으로 나오므로, 시간 초과가 발생할 수 있다.
따라서 이 경우는 예외 처리를 해주어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
int a, b, N; cin >> a >> b >> N;
if(a == 0 && b == 0 && N == 0) break;
if(a == 0 && b == 0) {
cout << 0 << "\n";
continue;
}
int ans = a + b;
N--;
while(N--) {
a = b;
b = ans;
ans = a + b;
}
cout << ans << "\n";
}
}
백준 BOJ 13171번 : A
문제 난이도 : Silver IV
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
a^b의 값을 구하는 문제이다.
분할 정복을 사용한 거듭제곱으로 풀이해줄 수 있다.
이 때 a는 처음부터 mod 값인 1e9 + 7을 넘어가서 주어질 수 있으므로, a는 거듭제곱 전에 mod 처리를 한 번 해주고 시작해야한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int a, b; cin >> a >> b;
int ans = 1, mod = 1e9 + 7;
a %= mod;
while(b > 0) {
if(b % 2 == 1) ans = (ans * a) % mod;
a = (a * a) % mod;
b /= 2;
}
cout << ans << "\n";
}
백준 BOJ 11288번 : Ethel's Encryption
문제 난이도 : Bronze I
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
어떤 암호문이 알파벳을 a^b만큼 shift하여 만들어졌다고 할 때, 원문을 구하는 문제이다.
알파벳은 총 26개이므로, a^b % 26만큼 shift 해주면 된다.
a^b는 분할 정복을 이용한 거듭제곱으로 구해줄 수 있다.
거듭제곱 연산마다 mod 26 처리를 해주어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, a, b; cin >> N >> a >> b;
cin.ignore();
string str; getline(cin, str);
int mul = 1;
while(b > 0) {
if(b % 2 == 1) mul = (mul * a) % 26;
a = (a * a) % 26;
b /= 2;
}
for(int i=0; i<str.length(); i++) {
if(str[i] == ' ') {
cout << " ";
continue;
}
str[i] = char('A' + (str[i] - 'A' - mul + 26) % 26);
cout << str[i];
}
cout << "\n";
}
백준 BOJ 11524번 : Immortal Propoises
문제 난이도 : Gold II
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
1,000개 이하의 테스트케이스에 대해 N번째 피보나치 수를 구하는 문제이다. (이 때 N ≤ 2^48)
같은 풀이를 위에서 여러 번 다루었으므로 설명은 생략한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int>> mat;
int mod = 1e9;
mat f(mat& v, mat& u) {
int N = 2;
mat w(N, vector<int>(N));
for(int i=0; i<v.size(); i++)
for(int j=0; j<u[0].size(); j++)
for(int k=0; k<v[0].size(); k++)
w[i][j] = (w[i][j] + v[i][k] * u[k][j]) % mod;
return w;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int t; cin >> t;
int N; cin >> N;
mat mul(2, vector<int>(2));
for(int i=0; i<2; i++) mul[i][i] = 1;
mat ba(2, vector<int>(2));
ba = {{1, 1}, {1, 0}};
while(N > 0) {
if(N % 2 == 1) mul = f(mul, ba);
ba = f(ba, ba);
N /= 2;
}
cout << t << " " << mul[0][1] << "\n";
}
}
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 백준 BOJ 문제 풀이 모음 : 그래프와 인접 행렬의 활용 220818 (0) | 2022.08.18 |
|---|---|
| 백준 BOJ 빠른 거듭제곱 알고리즘 (인접 행렬 활용 등) 문제 풀이 모음 (0) | 2022.08.17 |
| 백준 BOJ 최소 스패닝 트리 (MST) 문제 풀이 모음 220813 (0) | 2022.08.13 |
| 백준 BOJ Gold 난이도 구현 외 다양한 문제들 풀이 220812 (0) | 2022.08.12 |
| 백준 BOJ 구현, 시뮬레이션 문제 위주 풀이 모음 220811 (0) | 2022.08.11 |