acmi 님의 블로그

해당 글에서는 임의의 소수 p와 p미만의 자연수 n에 대해 n!(mod p)를 빠르게 구하는 방법에 대해 설명하고자 한다. 기본적인 풀이는 반복문으로 O(n)으로 푸는 것이다. 여기서 실제 실행시간에서 n에 곱해지는 상수를 줄일 수도 있고 fft를 이용하여 시간복잡도 O(sqrt(n)log^2(n)) 또는 O(sqrt(n)log(n))으로 구할 수도 있다. 이 글에서는 n에 곱해지는 상수를 줄이는 방법에 대해 설명할 것이다. 하지만 이 글에서 설명하는 방법은 fft를 이용하는 방법에도 적용이 가능하다. 상수를 줄이는 방법은 윌슨의 정리, barrett reduction, SIMD, 르장드르의 정리로 4가지가 있다. 4가지 방법은 모두 동시에 적용시킬 수 있다. 1. 윌슨의 정리윌슨의 정리에 의해 (p-1..

이 글에서는 c, c++에서 사용할 수 있는 숏코딩 방법을 설명한다. 하지만 다른 언어에서도 일부 방법을 사용할 수 있을 것이라 생각한다. 1. 변수 이름 바꾸기, 상수 다른 방식으로 표현하기변수의 이름을 짧게 바꾸면 가독성이 떨어질 수 있지만 코드의 길이를 (변수의 이름이 줄어든 길이)*(변수가 사용되는 횟수)만큼 줄일 수 있다. 상수는 1000000007을 1e9+7로 표현하거나 1048576(2의 20제곱)을 1 2. 반복문반복문에서 a번 반복해야할 경우 for(;a--;)또는 for(i=-1;++i 사용할 수 있다. 또한 반복문을 재귀함수로 바꾸었을 때 코드가 짧아지는 경우도 있다(길어질 수도 있다). 자료구조에서는 vector v; for(int a:v)와 같이 사용할 수 있다. 다차원 배열을 ..

해당 글에서는 USACO 2024 December Contest Silver 1, 2번 문제의 풀이를 간단히 설명하고자 한다. 1. Cake Game https://usaco.org/index.php?page=viewproblem2&cpid=1446 Elsie는 왼쪽, 오른쪽 끝에서부터 시작해서 연속하여 케이크를 원하는 대로 총합  N/2개를 먹을 수 있으므로 Elsie가 먹게 되는 케이크의 양은 처음 상태에서 Elsie만 N/2번 가져갈 때의 최댓값 이상이다.  Bessie는 다음과 같은 방법을 통해 Elsie가 최댓값보다 더 많이 가져가지 못하게 할 수 있다: 자신의 차례에서 놓여있는 짝수개의 케이크 중 가운데에 있는 두 케이크를 합친다. 이렇게 하면 Elsie의 차례에서 합쳐진 케이크는 홀수개의 케..

https://www.acmicpc.net/problem/13428알고리즘: fft 풀이(대문자와 소문자가 의미하는 바가 다르다):배열 a[i]와 b[i]를 각각 배열 A와 배열 B에서 i(0두 배열 a, b에 대해 합성곱에서 두 수의 곱셈을 두 수 중 크지 않은 것(c++에서 min함수)으로 바꾼 식을 계산하면 풀 수 있다(단, 배열 a, b의 크기 n은 200000이상으로 하고 100000부터는 a[i]와 b[i]는 0으로 하자). $ c[j]=\sum_{i=0}^{n-1}min(a[i],b[j-i])$ 나이브하게 계산하면 시간 복잡도는 $O(n^{2})$가 되고 시간초과가 난다. i와 j가 0 or 1일때 min(i,j)=i*j임을 이용하자.  f(x)를 x가 양수면 1, 그렇지 않으면 0으로 정의..

유클리드 호제법으로 gcd를 구하는 방법은 다음과 같다:두 자연수 a>b에 대하여 gcd(a,b)=gcd(b,a%b)임을 이용해 두 수 중 큰 것을 작은 것으로 나눠 그 나머지로 대체한다. 이 때 두 수 중 하나가 0이 되면 남은수가 gcd이다. 코드로 구현하면 다음과 같다:int gcd(int a,int b){//a>0, b>0if(b==0)return a;return gcd(b,a%b);}b>a%b이므로 다시 호출되었을 때는 a>b를 만족한다. 그러므로 b가 0인지만 확인하면 된다.a>b를 만족하지 않고 a>0, b>0이기만 해도 된다. 왜냐하면 a이면 gcd(b,a)가 다시 호출되기 때문이다. c언어에서는 a가 음수일 떄 a%b를 음수 또는 0으로 계산하므로 a>0, b>0이도록 해야한다. 양수로 ..