dh_0e

A, B가 $10^{16}$까지 이므로 $O(logn)$에 해결해야 한다.$O(n)$은 무조건 시간초과. 풀이 과정2진수에 나타나는 1의 개수를 구해보면 패턴을 찾을 수 있다.1{1}, 2~3{1, 2}, 4~7{1, 2, 2, 3}, 8~15{1, 2, 2, 3, 2, 3, 3, 4} 까지만 봐도 패턴이 보인다.d[i] = $2^i$ ~ $2^{i+1}-1$에서 1의 개수라고 했을 때 점화식은 $d[i]=d[i-1]*2+2^{i-1}$로 구할 수 있으며 이를 각 구역으로 봤을 때, 각 구역별로 절반씩 나눠보면 똑같은 패턴인 것이 확인된다.8~15{1, 2, 2, 3, 2, 3, 3, 4}를 반으로 나누면 8~11{1, 2, 2, 3}, 12~15{2, 3, 3, 4}로 나눠지고 반으로 나눈 right ..

조합론이 기본이 되는 문제로 계산식 발상에 좀 애먹은 문제결론적으로 메뉴들을 맵기 순으로 정렬하면, 메뉴마다 가장 높은 수치, 낮은 수치일 경우의 수가 정해져 있으므로 각각의 메뉴마다 경우의 수를 조합론으로 구해 계산해주면 된다. 풀이과정한 메뉴가 포함되는 조합의 수는 총 $2^{n-1}-1$가지이다.하지만 스코빌 수치가 이용되는 경우만 따지면 되기 때문에 i번째 메뉴가 가장 높은 스코빌 수치일 때와 가장 낮을 때만 구해주면 된다. 식으로 나타내면 다음과 같다. (i가 0~n-1일 때)가장 높은 스코빌 수치일 경우 >> $2^i-1$가장 낮은 스코빌 수치일 경우 >> $2^{n-i-1}-1$i번째 메뉴보다 높거나 낮은 스코빌을 선택할 때 모두 선택하지 않은 경우의 수가 있기 때문에 -1을 해줌 $2^n$..

비트마스킹을 활용한 dp 문제, 근데 이제 큰 수 % k를 곁들인 .. 시행 착오 vector > dp[][]로 선언을 하여 dp[i][j] = i개의 원소를 합쳤을 때, 마지막 원소에 j번째 원소를 삽입한 pair(first = 지금까지 삽입한 원소들의 비트마스킹, second = k로 나눈 나머지)를 삽입하는 것으로 점화식을 짰다.이 후에 말도 안 되는 메모리 초과를 보여주며 전처리 및 메모리도 줄인 후 진행했는데 여전히 답이 안 보였다. 해결 방안갈아엎었다. 점화식부터 다시 구상하니 dp[i][j] = 지금까지 사용한 원소를 마스킹한 값이 i, 나머지가 j인 수열의 갯수 로 풀 수 있었다.전처리 및 dp에 각각 하나씩 사용한 경우의 수 저장ten_mod에 10^l 들을 k로 나눈 나머지를 모두 구해..