[Medium] YetAnotherORProblem

P = A[0] | A[1] | ... | A[n-1] 이라 하자. P를 이진수로 나타냈을 때 만약 i번째 비트가 켜져있다면 i번째 비트가 켜져있는 A[j] (0 <= j < n) 가 적어도 하나 이상 존재한다. 여기에서 더 나아가 i번째 비트가 켜져있는 A[j] 는 단 1개이다. 만약 i번째 비트가 켜져있는 것이 2개 이상이라면 sum(A[j]) 가 P 보다 커지기 때문이다. 따라서 P의 켜져있는 비트에 대해, 그 비트를 A[0] 부터 A[n-1] 중 하나에 배정하는 경우의 수를 세면 된다. A[0] 부터 차례차례 만들어나가는 전형적인 접근방법이 이 문제에선 잘 들어맞지 않는다. 0 <= A[j] <= R[j] 라는 조건을 만족시켜야 하기 때문이다. 각 비트마다 하나의 A[j] 만을 골라 비트를 배정해줘야한다는 것에 착안해서 62번 비트부터 비트별로 만들어나가는 dp를 생각할 수 있다. 62번 비트부터 i번 비트까지는 A[j]를 R[j] 와 똑같이 배정하다가 i-1번 비트에서 R[j]보다 A[j]가 작도록 비트를 배정한다면 그 이후로는 아무렇게나 비트를 배정해도 A[j] < R[j] 를 만족한다. 따라서 현재 j번째 수가 A[j] < R[j] 인지 A[j] == R[j] 인지를 구분하는 상태가 dp에 필요하다. D[i][s] = 62번 비트부터 i번 비트까지 조건을 만족하는 비트할당의 경우의수 s는 현재 A[j] < R[j] 인 j의 집합 D[i][s] 를 구하기 위해 s의 부분집합인 p에 대해 D[i+1][p] 를 고려할 수 있다. s와 p의 관계를 고려해서 A[0] ~ A[n-1] 중 하나에 i번 비트를 1로 배정하거나, 모두 0으로 배정하는 경우를 따져서 경우의 수를 잘 세어주면 된다.