[CodeForces - 1062C] Banh-mi

난이도: 1600

 

태그

• Greedy
• Prefix Sum

 

풀이

1. 하나의 배열에서, 신경써야 하는 건?

하나의 배열에서 신경써야 하는 건 그 배열 속의 0과 1의 개수 뿐입니다.

 

2. 무슨 순서대로 처리해야 할까?

Exchange Argument를 생각해보면, 큰 값부터 사용해야 합니다.

// 더 작은 값을 먼저 사용한다면, 그 뒤에도 작은 수가 더해져서 답이 더 작아지기 때문이죠.

 

3. 이 때의 답은?

이를 적용시키면, 우선 모든 1을 처리한 뒤 모든 0을 처리해야 함을 알아차릴 수 있습니다.

 

이제 1이 어떻게 처리되는지 봅시다.

1번째 수는 1이 됩니다.

2번째 수는 1+1 = 2가 됩니다.

3번째 수는 1+1+2 = 4가 됩니다.

4번째 수는 1+1+2+4 = 8이 됩니다.

...

 

2의 제곱수로 더해지는 걸 볼 수 있습니다.

그러므로, 지금부터 \( T_c = 1 + 2 + 4 + \ldots + 2^{c-1} = 2^c - 1 \)를 따로 저장해봅시다.

 

위와 같이 모든 1을 제거한 뒤에는, 0을 제거해야 합니다.

하지만, 이 시점이 되면 모든 0은 \( T_c \)라는 값으로 변경되어있습니다.

 

이는 그냥 1 대신 \( T_c \)를 들고 문제를 푸는 것과 동일하므로, \( T_c \times T_d \)가 답에 추가로 더해집니다.

 

4. 코드

const ll mod = 1e9 + 7;
int arr[100020]; pi2 prf[100020];
 
const int N = 100000;
ll one[100020];
 
void Main(){
    for (int i = 1; i <= N; i++){ one[i] = (one[i-1]*2 + 1) % mod; }
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++){
        char ch; cin >> ch; arr[i] = ch&1;
    }
    for (int i = 1; i <= n; i++){
        prf[i] = prf[i-1];
        (arr[i] == 0 ? prf[i].fr : prf[i].sc) += 1;
    }
    while (q--){
        int l, r; cin >> l >> r;
        pi2 cnt = {prf[r].fr-prf[l-1].fr, prf[r].sc-prf[l-1].sc};
        ll ans = one[cnt.sc] + one[cnt.sc]*one[cnt.fr] % mod;
        cout << ans%mod << endl;
    }
}