본문 바로가기

수학5

[백준 16998] It's a Mod, Mod, Mod, Mod World [Diamond IV] https://www.acmicpc.net/problem/16998 16998번: It’s a Mod, Mod, Mod, Mod World You are given multiple problems with three integers p, q, and n. Find \(\displaystyle\sum_{i=1}^{n}{((p \cdot i) \text{ mod } q)}\). That is, the first n multiples of p, modulo q, summed. Note that the overall sum has no modulus. www.acmicpc.net \( \sum_1^n {\left( pi \bmod q \right)} \)의 값을 구하는 문제. 50만 개 정도의 쿼리가 주어지는데.. 2023. 2. 19.
[백준 21117] Number of Colorful Matchings [Ruby III] https://www.acmicpc.net/problem/21117 21117번: Number of Colorful Matchings Output $n + 1$ lines containing your answers for $k = 0, 1, 2, \ldots, n$ respectively. Remember that you only need to output the answer modulo $2$. www.acmicpc.net 알아두어야 할 배경지식이 몇 개 있다. 자세한 사항은 https://en.wikipedia.org/wiki/Permanent_(mathematics) 여기를 참고했다. 1. 이분 그래프 G의 adjoint matrix는 \( \begin{bmatrix} O & A \\ A^T & O.. 2023. 2. 6.
고속 푸리에 변환, 이론부터 구현까지 1. 구현하기 전에 필요한 지식 고속 푸리에 변환(Fast Fourier Transform; FFT)은 어떤 벡터의 이산 푸리에 변환을 \( O(n \log n) \) 안에 구할 수 있게 해주는 쉬우면서도 강력한 알고리즘이다. 푸리에 변환이라고 하니 굉장히 생소해 보이고, 신호 처리나 미분방정식 푸는 데 외에는 쓸데가 없어 보이지만, 사실 이걸 갖고 상당히 많은 일을 할 수가 있다. 예를 들자면 차수가 n인 두 다항식을 \( O(n \log n) \)에 곱한다. (가장 직관적인 방법으로 계산하면 \( O(n^2) \)이 나오게 된다.) 크기가 \( 10^n \) 정도인 두 자연수를 \( O(n \log n) \)에 곱한다. (마찬가지로 직관적으로 곱하면 \( O(n^2) \)이다.) 자연수 집합의 두 부.. 2023. 1. 2.
[대학생 수학경시대회] 2014년 제1분야 8번 8. 양의 무리수 \( \alpha \)에 대하여 수열 \( \left\{ q_n \right\}_{n \geq 1} \)을 $$ q_n = {[n \alpha] \over n} $$ 로 정의하면 수열 \( \left\{ q_n \right\}_{n \geq 1} \) 은 단조증가수열이 아님을 보여라. Sol) 일반성을 잃지 않고 \( 0 2022. 8. 29.
[대학생 수학경시대회] 2021년 제2분야 6번 대한수학회에서 공식 제공하는 대학생 수학경시대회의 해설은 깔끔한 풀이보다는 색다른 풀이를 선호하는 경우가 많다. 그래서 여러 가지 방법으로 풀 수 있는 문제들에 대해서는 여러 풀이를 알아두는 것이 좋다. '행렬의 고유벡터는 그 행렬을 설명하는 특성 중 하나다'를 잘 나타내주는 문제라고 생각한다. 2022. 8. 28.

티스토리툴바