백준/수학 (28) 썸네일형 리스트형 백준 10736 - XOR삼형제 2 https://www.acmicpc.net/problem/10736 수열의 최대 길이 찾기 XOR의 성질에 따라 $V \oplus V = 0$ 이므로 XOR 과정 중 중복되는 수를 만나서는 안된다. 다시 말해 어떤 세 원소를 선택하든 최소 한 개의 비트를 살릴 수만 있으면 된다는 것이다. 그렇다면 100 이하의 수로 구성할 수 있는 수열의 최대 길이는 어떻게 찾을 수 있을까? 32와 64를 이진수로 나타낸 표를 보면서 생각해보자. X 1 0 0 0 0 0 1 0 0 0 0 0 0 이 표에 존재하는 0을 0 혹은 1로 채우는 경우의 수를 만든다고 했을 때 1이 절대로 들어가서는 안 되는 경우가 무엇일까? X 1 0 0 0 0 0 1 NO 0 0 0 0 0 바로 64에서 $2^{5}$에 해당하는 비트이다. .. 백준 4375 - 1 https://www.acmicpc.net/problem/4375 수 뒤에 계속 1을 붙여나가면서 배수가 성립하는지 확인하면 된다. 다만 이 과정에서 오버플로우가 발생할 수 있다. 큰 정수를 구현해서 풀 수도 있겠지만 1을 붙이면서 n으로 나눈 나머지만을 남겨 불필요한 부분을 제거하면 int 자료형을 이용하여 문제를 풀 수 있게 된다. 전체 코드 더보기 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; while (!cin.fail()) { int cnt = 1; int x = 1; while (x) { x %= n; if (!x) break; x *= 10; ++x; ++c.. 백준 13172 - Σ https://www.acmicpc.net/problem/13172 문제 요약 $N_{i}, \: S_{i}$가 M개 주어지는데 이들을 $a \times (b^{-1} \mod p)$ (p는 소수)의 형태로 바꾸고 그 합의 모듈러를 구하라. 풀이 문제에서 페르마의 소정리를 사용하라고 했으므로 페르마의 소정리를 통해 $N_{i} \mod p$를 구한 뒤 $S_{i}$를 곱하면 된다. 문제의 이름처럼 기대값들을 모두 더하는 것을 잊지 말자. 전체 코드 더보기 #include using namespace std; using ll = long long; #define mod 1000000007 int m; ll pomod(ll val, int b) { if (b == 1) return val % mod; if .. 백준 11444 - 피보나치 수 6 https://www.acmicpc.net/problem/11444 최대 $10^{18}$ 번째 피보나치 항을 구해야 한다. 피보나치 수의 n번째 항 $F_{n}$은 다음과 같은 행렬 제곱으로 나타낼 수 있음이 알려져있다. $\begin{pmatrix} F_{n + 1} & F_{n} \\ F_{n} & F_{n - 1} \end{pmatrix}^{n}$ 분할 정복을 이용한 거듭제곱을 활용하여 원하는 항을 빠르게 구하면 된다. 전체 코드 더보기 #include using namespace std; using ll = long long; ll mod = 1e9 + 7; ll n; struct mat_fibo { vector mat; mat_fibo(): mat(2, vector(2)) {} mat_fibo.. 백준 1413 - 박스 안의 열쇠 www.acmicpc.net/problem/1413 문제의 상황을 상상해보자. 박스에 열쇠를 넣다 보면 열쇠로 다른 박스를 여는 상황이 마치 방향 그래프를 구성하는 것처럼 보임을 알 수 있다. 5번 박스에 5번 열쇠가 있다면 이는 루프를 가진 그래프가 되는 것이다. 박스와 열쇠의 관계는 여러개의 사이클 그래프가(루프 포함) 나오는 것으로 생각할 수 있고, 이는 제1종 스털링 수로 환원된다. 제1종 스털링 수는 말 그대로 n개의 노드에서 m개의 사이클이 형성되는 경우를 나타내는 수열이다. 제1종 스털링 수의 점화식은 다음과 같다. $s(n, k) = (n - 1)s(n - 1, k) + s(n - 1, k - 1) \; (s(0, 0) = 1)$ 한 사이클을 순회하기 위해선 한 개의 폭탄이 필요함을 알 수.. 이전 1 2 3 4 5 6 다음
