[Codeforces 1084C] The Fair Nut and String

[Codeforces 1084C] The Fair Nut and String

난이도 1500짜리라서 얕봤다가 호되게 당한 문제이다. 처음에 버추얼로 돌 때는 10분만에 솔루션은 나왔는데 그것과 관련된 개념을 잘 몰라서 못 풀었다. 일단 결론부터 얘기하자면 이 문제는 b를 기준으로 분할했을 때, 연속해서 등장하는 a의 개수들이 있을텐데 그 개수로 집합의 원소로 구성해서 그 집합의 모든 부분집합의 곱들의 합이 곧 답이다. 예를 들어 설명하자면 " abaabaaa " 라는 문자열이 있다면 b를 기준으로 a의 개수를 {1,2,3}이 된다. 그래서 {1,2,3}으로 만들 수 있는 부분집합들의 원소들의 곱들의 합(=23)이 답이 된다. 이 연산을 단 O(N)만에 수행하는 공식이 존재하는데 나는 몰라서 naive하게 2^N 풀이밖에 몰랐다. 그래서 구글링해서 검색해본 결과 "Sum of products of all possible subsets"이라고 검색하니 나오더라. 그래서 단 O(N)만에 계산하는 공식은 다음과 같다. 

집합의 원소를 {a1,a2....a_n}이라고 할 때, Sum = (1+a1)(1+a2)....(1+a_n) - 1

간단하게 증명을 하자면 dp의 개념을 사용해야 한다.

만약 현재 i번 째까지의 원소의 곱들의 합을 dp[i]라 하고, 다음 (i+1)번 째를 구한다고 하자. (i+1)번 째 원소를 val[i+1]이라고 한다면 dp[i+1]은 다음 두 경우의 합과 같다.

  ① 기존의 구한 합(=dp[i])       ②val[i+1]번 째를 추가함으로써 새롭게 추가된 합(=dp[i]×val[i+1])

따라서 이를 정리하면 dp[i+1] = dp[i]×( 1 + val[i+1] )이 된다. 이를 n번 째 원소까지 똑같이 적용하면 위의 식처럼 된다. 그리고 마지막에 1을 빼는 것은 (1+ ~)의 형태에서 ' 1+' 처리하기 위함이다. 마지막에 1이 남는 것은 dummy라고 생각하면 된다.  

#include<stdio.h>
#include<vector>
using namespace std;
#define SIZE 100009
const int MOD=(1e9+7);
char str[SIZE];
int main(){
    scanf("%s",str+1);
    vector<int> v;
 
    for(int i=1,cnt=0 ; str[i] ; i++){
        if(str[i]=='a'){
            cnt++;
        }
        if(str[i]=='b' || str[i+1]==0 ){
            if(cnt) v.push_back(cnt);
            cnt=0;
        }
    }
 
    long long ans=1;
    for(int i=0 ; i<v.size() ; i++){
        ans=ans*(1+v[i]) % MOD;
    }
    ans--;
    printf("%lld\n",ans);
    return 0;
}