Codeforce #515 Binary Numbers AND Sum

Codeforce #515 Binary Numbers AND Sum

문제 원본

---

문제설명

입력 조건

2개의 이진수 자리수 n,m

자리수 만큼 이진 수가 들어온다.

이진수 a 와 b를 and 연산 한 값을 구한 뒤 b를 오른쪽으로 shift연산을 한다.

다음 a와 이전에 b를 오른쪽으로 shift 여산한 값을 and연산 한 값을 구한뒤 현재 b를 shift한다.

b가 더이상 shift할수 없을 때 까지 반복한다.

---

문제 풀이

1 step

    이진수 a를 전처리 한다.

    전처리 방법은 누적합을 구한다.

    ex)

        이진수 1010이 주어지면  비트가 켜신곳에 2의 지수승을 더하고 이전 인덱스에 최종적인 합을 누적해서 보관한다.

        만약 b의 이진수 길이가 더 클경우 부분합 배열을 b의 이진수 길이 만큼 구한다.

        위의 배열의 값은 첫 번째 자리수에서 현재 인덱스 까지 이진수 a의 켜져 있는 비트를 누적한 값이다

        위의 정의가 중요하니 꼭 상기 시키고 다음 스텝으로 넘어간다.

2 step

    위 화살표로 표신 되어 있는 구간이 이진수 b가 켜져 있을 때 켜져 있는 a비트들과의 합들이 우리고가 구하려는 값에 더해질 수 있다.

    우리는 1step에서 미리 구해 놓은 배열이 이진수 a의 켜져있는 비트의 합을 미리 구했기 때문에 부분 똑같은 연산을 중복으로 할 필요가 없으므로 해당 부분합을 그대로 더하면 된다.

---

소스 코드