🙌

AGC 031 | A - Colorful Subsequence

2020/12/20に公開

競プロ

文字列

組み合わせ

tech

問題

解法

ポイントは以下である。

すべて異なる文字
文字列として同一でも、異なる位置から取り出された部分列は区別して数えることする

上記より同じアルファベットは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;
}

AGC 031 | A - Colorful Subsequence

問題

解法

コード

参考

Discussion