수학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 ∑i=1n((p⋅i) mod q). That is, the first n multiples of p, modulo q, summed. Note that the overall sum has no modulus. www.acmicpc.net ∑1n(pimodq)의 값을 구하는 문제. 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,…,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(nlogn) 안에 구할 수 있게 해주는 쉬우면서도 강력한 알고리즘이다. 푸리에 변환이라고 하니 굉장히 생소해 보이고, 신호 처리나 미분방정식 푸는 데 외에는 쓸데가 없어 보이지만, 사실 이걸 갖고 상당히 많은 일을 할 수가 있다. 예를 들자면 차수가 n인 두 다항식을 O(nlogn)에 곱한다. (가장 직관적인 방법으로 계산하면 O(n2)이 나오게 된다.) 크기가 10n 정도인 두 자연수를 O(nlogn)에 곱한다. (마찬가지로 직관적으로 곱하면 O(n2)이다.) 자연수 집합의 두 부.. 2023. 1. 2. [대학생 수학경시대회] 2014년 제1분야 8번 8. 양의 무리수 α에 대하여 수열 {qn}n≥1을 qn=[nα]n 로 정의하면 수열 {qn}n≥1 은 단조증가수열이 아님을 보여라. Sol) 일반성을 잃지 않고 \( 0 2022. 8. 29. [대학생 수학경시대회] 2021년 제2분야 6번 대한수학회에서 공식 제공하는 대학생 수학경시대회의 해설은 깔끔한 풀이보다는 색다른 풀이를 선호하는 경우가 많다. 그래서 여러 가지 방법으로 풀 수 있는 문제들에 대해서는 여러 풀이를 알아두는 것이 좋다. '행렬의 고유벡터는 그 행렬을 설명하는 특성 중 하나다'를 잘 나타내주는 문제라고 생각한다. 2022. 8. 28. 이전 1 다음
