[AtCoder - ABC104 D] We Love ABC

난이도: 1739

 

태그

• Double Counting
• Combinatorics
• Prefix/Suffix Query

 

풀이

1. '?'를 제외하고 생각해보자.

문자열에 '?'가 없다고 가정해봅시다.

그럼, 문제의 답은 그냥 만들 수 있는 "ABC"의 개수가 됩니다.

 

이 개수는 어떻게 찾을까요?

 

중심에 있는 'B'를 하나로 고정해봅시다.

그럼, 그 문자를 사용해서 만들 수 있는 "ABC"의 개수는 왼쪽에 있는 'A'의 개수 × 오른쪽에 있는 'C'의 개수가 됩니다.

 

문제의 답은 이를 모든 'B'에 대해 고려해주면 됩니다.

// 중심에 있는 'B'가 다르기 때문에, 한 문자열을 두번 셀 걱정은 하지 않아도 됩니다.

 

2. 어떤 문자 'B'를 고정시킬 때, '?'를 포함해서 계산하는 방법은?

이제 '?'가 들어오기 때문에, 왼쪽에 있는 'A'와 왼쪽에 있는 '?'의 개수를 같이 고려해줘야 합니다.

오른쪽 역시 'C'와 '?'를 같이 고려해야겠죠.

 

여기서는 왼쪽의 경우만 고려하겠습니다. 오른쪽도 Suffix일 뿐 사실상 동일합니다.

 

만약 'A'가 \( a \)개 있고, '?'가 \( b \)개 있다고 생각해봅시다.

이 때 가능한 모든 문자열에 대해 중심의 'B'를 포함시켜서 만들 수 있는 "ABC"의 총 개수는 아래와 같이 생각해볼 수 있습니다.

 

만약 \( b \)개의 '?' 중 \( c \)개를 'A'로, 나머지를 'B' or 'C'로 변환해본다고 합시다.

이는 \( _bC_c \times 2^{b-c} \)가지 경우가 있습니다.

그리고, 각각의 경우에 대해 생기는 'A'는 \( a+c \)개가 됩니다.

즉, 최종 값은 \( (a+c) \times {}_bC_{c} \times 2^{b-c} \)가 됩니다.

 

이를 \( c = 0 \)부터 \( c = b \)까지 돌려보면, \( \sum\limits_{c=0}^{b} \left( (a+c) \times {}_bC_{c} \times 2^{b-c} \right) \)가 나옵니다.

// 여담으로, [1]에서 했던 곱하는 걸 유지해도 되는가에 걱정을 할 수도 있습니다.

// 다행히도, 곱하는 건 왼쪽에서 하나 선택 × 오른쪽에서 하나 선택 의 합이므로, 합의 곱으로 나타낼 수 있습니다.

 

3. 문제의 답을 빠르게 계산하는 방법은?

[2]의 과정을 그대로 하기에는, \( O(N) \)가지 Prefix를 계산하는데 \( O(N^2) \)의 시간이 걸리게 됩니다.

 

대신, Prefix에 한 글자씩 추가하면서 계산해봅시다.

지금까지 봤던 글자 중 'A'의 개수를 \( a \), '?'의 개수를 \( b \)라고 합시다.

 

잠시 \( a = 2, b = 3 \)이라고 해봅시다.

그럼, 아까 계산한 식을 항 단위로 나눠서 아래와 같이 쓸 수 있습니다.

// (위 × 아래)를 합한다고 생각해보세요.

\( _0C_3 \times 2^3 = 8 \)	\( _1C_3 \times 2^{3-1} = 12 \)	\( _2C_3 \times 2^{3-2} = 6 \)	\( _3C_3 \times 2^{3-3} = 1 \)
\( 2+0 = 2 \)	\( 2+1 = 3 \)	\( 2+2 = 4 \)	\( 2+3 = 5 \)

 

이제, 이 값이 새로운 값으로 달라질 때는 아래 두 경우로 나눠볼 수 있습니다.

• 새로운 'A'를 발견:
  아래쪽에 1씩 더하는 경우입니다.
  즉, 문제의 답에는 \( \sum\limits_{c=0}^{b} {}_bC_{c} \times 2^{b-c} \)가 더해지겠죠.
  그런데, 이항 정리에 따르면 위 식은 \( (2+1)^b \)로 나타낼 수 있습니다.
  그러니, 그냥 답에 \( 3^b \)가 더해지는 거겠죠.
• 새로운 '?'를 발견:
  새로운 '?'는 'A'이거나, 'B' or 'C'로 변환될 수 있습니다.
  만약 변환 결과가 'A'였다면, 아래쪽의 값에 1씩 더해져야겠죠.
  다르게 보자면, 위쪽의 값을 오른쪽으로 1씩 미는 거라고 보면 됩니다.
  반대로 'B' or 'C'라면, 가능한 글자가 2가지였으므로 현재 위치에 2가 곱해집니다.
  즉, 식은 \( 2 \sum\limits_{c=0}^{b} \left( (a+c) \times {}_bC_{c} \times 2^{b-c} \right) + \sum\limits_{c=0}^{b} \left( (a+c+1) \times {}_bC_{c} \times 2^{b-c} \right) \)가 됩니다.
  그런데, 이를 조금 더 생각해보면, 오른쪽 값을 전개해서 식을 \( 3 \sum\limits_{c=0}^{b} \left( (a+c) \times {}_bC_{c} \times 2^{b-c} \right) + \sum\limits_{c=0}^{b} {}_bC_{c} \times 2^{b-c} \)로 만들 수 있습니다.
  이 식은 아까 위에서 본 식이고, 이 값은 \( 3^b \)이죠.
  그러므로, 지금까지 구한 답에 3을 곱하고 \( 3^b \)를 더해주면 됩니다.

 

이제 이걸 Prefix와 Suffix에 대해 모두 계산한 뒤, 각 위치에 대해

그 위치가 'B'거나 '?'일 때마다 prefix × suffix를 구해서 합해주면 됩니다.

 

4. 코드

const ll mod = 1e9 + 7;
pi2l prf[100020], suf[100020];
 
void Main(){
    string s; cin >> s; int n = s.size(); s = " " + s;
    ll val = 1; for (int i = 1; i <= n; i++){
        prf[i] = prf[i-1];
        if (s[i] == 'A'){
            prf[i].fr.fr += 1;
            prf[i].sc += val; prf[i].sc %= mod;
        }
        if (s[i] == '?'){
            prf[i].fr.sc += 1;
            prf[i].sc *= 3; prf[i].sc += val; prf[i].sc %= mod;
            val = val*3 % mod;
        }
        //cout << "PRF " << i << " = " << prf[i].fr.fr << ' ' << prf[i].fr.sc << ' ' << prf[i].sc << endl;
    }
    val = 1; for (int i = n; i >= 1; i--){
        suf[i] = suf[i+1];
        if (s[i] == 'C'){
            suf[i].fr.fr += 1;
            suf[i].sc += val; suf[i].sc %= mod;
        }
        if (s[i] == '?'){
            suf[i].fr.sc += 1;
            suf[i].sc *= 3; suf[i].sc += val; suf[i].sc %= mod;
            val = val*3 % mod;
        }
        //cout << "SUF " << i << " = " << suf[i].fr.fr << ' ' << suf[i].fr.sc << ' ' << suf[i].sc << endl;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++){
        if (s[i] == 'B' || s[i] == '?'){ ans += prf[i-1].sc*suf[i+1].sc%mod; ans %= mod; }
    }
    cout << ans;
}