뉴비의 PS 낙서장

2차원 배열이 있다고 생각해보면 위에서 아래로 누적합을 한번 하고 왼쪽에서 오른쪽으로 누적합을 한번한다면, 누적합 배열이 만들어 진다. 이제 그러면 포함-배제의 원리를 이용하여 누적합 배열을 채우면 O(2048N) 으로 시간초과가 나지만 이제 11차원으로 늘려보면 11번의 뱡향으로 밀면 된다는 것을 알 수 있다. 그래서 저 방법을 사용하면 O(11N) 으로 11차원 누적합 배열을 전처리 할 수 있다. Do : 지금 쿼리가 a[ret[0][0]~ret[0][1]][ret[1][0]~ret[1][1]] ... [ret[10][0]~ret[10][1]] 일때 값 구하기, 포함-배제의 원리를 사용하는 2차작업 f : 포함-배제의 원리를 사용하는 1차작업 쿼리를 처리할때는 포함-배제의 원리를 사용해도 시간이 충분..

C++ 로 조합을 구현하는 방법을 알려주겠다. nCr = n-1Cr-1 + n-1Cr 라는 식을 이용하여 O(nr) 만에 구하는 방법도 있지만, n,r 이 10만정도 된다면 메모리도 시간도 펑펑 터질 것이다. 그래서 이번 글에는 조합을 빨리 구하는 방법을 알려주겠다. (와아앙아앙아아 짝짝짝짝) 순서는 STL내장함수인 next_permutation 을 사용해서 출력하면된다. (이 글은 나중에 추가될 예정이다) 조합을 구할려면 일단 식을 보자 조합 식 이제 이 식을 직접 구하면 되는데 n! 을 구하고 r! 을 구하려고 하면 mod 값에 나눠버리는 경우가 있어서 매우 까다롭다. 예를 들어보자. mod = 7, 구하려고 하는 수는 5C3 이다. 그러면 5! 을 구하고 3! 을 구하고 2! 을 구하고 5! 구한것..

5분안에 마스터 하는것이기 때문에 아주 간결하고 핵심 요약만 말할것이다. 준비물 : hash에 대한 기본 지식, 이분탐색에 대한 기본 지식 1. 이분탐색을 돌린다. 길이가 i인 문자열이 반복으로 나온다면 그 아래는 볼 필요가 없다. 즉 이분탐색이 가능하다. 2. hash테이블을 이용하여 같은 문자열이 있는지 검사한다. hash테이블을 써서 길이 i인 것들중 같은것이 있는지 체크해준다. (hash에 대한 기본지식은 알고 있기 바란다.) 시간 복잡도는 O(NlogN) 이다 아래의 코드는 3033 번 문제이다. 바로 코드를 보겠다. #include using namespace std; const int mod = 100003; int f(long long x) { // x % mod 를 양수로 만들어주는 함수..