BOJ 15485 - a^ib^jc^k

BOJ 15485 - (a^ib^jc^k)

$b^jc^k$ 의 개수부터 세보자.

뒤부터 순회하며 어떤 $b$를 만났을 때, 거기서 그 $b$를 꼭 포함시켜서 만들 수 있는 $b^jc^k$ 의 개수에 현재 $b$ 앞에 있는 $a$의 개수로 만들 수 있는 $a^i$ 의 개수를 곱해줘서 정답에 더해주면 된다.

const ll mod = 1e9 + 7;
inline ll md(ll x) { return md(mod, x); }
int pw2[1000001];
void solve() {
   string s;
   cin >> s;
   int n = sz(s);
   pw2[0] = 1;
   for (int i = 1; i <= 1000000; i++) pw2[i] = md(pw2[i - 1] * 2);
   int a = cntt(s, 'a');
   int ans = 0;
   for (int i = n - 1, c = 0, dp = 0, dpsum = 0; i >= 0; i--) {
      if (s[i] == 'b') {
         dp = md(dpsum + (pw2[c] - 1));
         dpsum = md(dpsum + dp);
         ans = md(ans + dp * (pw2[a] - 1));
      } else if (s[i] == 'c') c++;
      else if (s[i] == 'a') a--;
   }
   cout << ans;
}