미분당한 적분상수

10986 나머지 합(acmicpc.net) 어떤 수열의 부분합이 M으로 나누어 떨어지는 구간의 개수를 구하는 문제이다. 모든 부분합에 대해서 경우의 수를 세어주면 O(N2)의 시간에 해결할 수 있다.하지만 N의 범위가 106까지 이므로이 시간 복잡도로는 문제를 해결할 수 없다. A의 누적합 배열을 prefix라 하고잘 생각해 보면 우리가 원하는 경우는(prefix[j] - prefix[i-1])%m == 0인 경우이다. (i  이를 풀어보면prefix[j]%m - prefix[i-1]%m == 0prefix[j]%m == prefix[i-1]%m을 얻을 수 있다. 서로 나머지가 같은 것을 선택하면 서로 상쇄하기 때문에(부분합을 구할때 prefix[j] - prefix[i-1] 를 하는 것을 생각해보면 ..

2143 두 배열의 합(acmicpc.net) A,B 두 배열이 주어지고이 두 배열의 부분합의 합이 T가 되는 경우를 구하면 되는 문제이다. 이 문제의 해결 방법으로는 누적합+이분탐색, 누적합+map 정도 있는 것 같다.좀 더 직관적이라고 생각하는 누적합+map 풀이에 대해 설명하겠다. N의 범위가 1이므로 상당히 여유롭다.이 단서를 가지고 조금 무식하게 접근해 볼 것이다. 부분합의 대한 정보를 사용해야하므로당연히 A와 B의 누적합을 필요로 한다. naïve하게 모든 경우를 다 구해볼 경우에는 통과가 가능할까 생각해보자.vector Aprefix, Bprefix;for(int i=0; iA배열에서의 모든 부분합을 구할 때 O(N2)B배열에서의 모든 부분합을 구할 때 O(N2)이 두 경우에 대해 모든 조합..

https://atcoder.jp/contests/abc295/tasks/abc295_d D - Three Days Ago AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 인상적인 풀이가 있다. 먼저 평범한 풀이는 1. 문자열 s로 입력을 받는다. 2. s의 i번째 요소(0~9) 각각의 누적합을 작성한다. (짝수 홀수만 판단하면 되므로 0,1로 기록한다.) 3. i가 0~s.size() 일 때, i에 대해 기록된 누적합(0~9)을 2진법을 생각하고 10진법으로 변환하여 masking벡터에 저장한다. (이 과정에서 비트 마..