AGC 031 | A - Colorful Subsequence

문제.

https://atcoder.jp/contests/agc031/tasks/agc031_a

해법

요점은 다음과 같다.

모든 다른 문자

문자열로 같아도 서로 다른 위치에서 추출한 부분 열을 구분하여 계산한다

위와 같은 자모는 1개 또는 0개만 사용할 수 있다.그림에서 보듯이 아래와 같다.

이 조합을 직접 곱하고 마지막에 0개 조합(빈 문자)을 모두 사용한 부분을 1개를 빼면 답이 필요하다.

코드

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

using mint = modint1000000007;

// アルファベットごとに注目すると同じアルファベットを1つ選ぶか0個選ぶかである。
// この組み合わせを各アルファベットでかけて最後に全部0個選んだ1通りを引けば答え
int main() {
  ll n;
  string s;
  cin >> n >> s;
  mint ans = 1;
  unordered_map<char, ll> cnt;
  for (int i = 0; i < n; i++) {
    char c = s[i];
    cnt[c]++;
  }
  for (auto [k, v] : cnt) {
    ans *= (v + 1);
  }
  cout << ans.val() - 1 << endl;
}

참고 자료

https://atcoder.jp/contests/agc031/editorial