AtCoder AGC 031 A - Colorful Subsequence (緑色, 200 点)

高校数学を思い出させてくれる感じの数え上げ問題

問題へのリンク

問題概要

長さ の文字列 が与えられる。

の部分列であって、すべて異なる文字からなるものの数を 1000000007 で割った余りを答えてください。文字列として同一でも、異なる位置から取り出された部分列は区別して数えることとします。

制約

• 

考えたこと

まず以下の設定は根本的に異なることに注意が必要だったり

• 同じ文字を異なる位置から取り出すのは区別する
• 同じ文字を異なる位置から取り出すのは区別しない

このどちらの設定かによって、かなり根本的に違う問題になってしまう。一般には前者の方が簡単。

今回は結局以下のような問題になる。

• S 中のどの 'a' を選ぶか、または 'a' を採用しないかを決める
• S 中のどの 'b' を選ぶか、または 'b' を採用しないかを決める
• ...
• S 中のどの 'z' を選ぶか、または 'z' を採用しないかを決める

それぞれ文字 c について、それが num 個あるとき取りうる選択肢は num + 1 通りになる。

よって、求める場合の数は各文字 c についての

(c の登場回数) + 1

を掛け算すればよい。振り返って、この問題でポイントとなるのは

• S の中の文字の並びはまったくどうでもいい

ということ。

• S = "ababca"
• S = "aaabbc"

の両者は同じ。

#include <iostream>
#include <string>
using namespace std;
const long long MOD = 1000000007;
 
long long num[30];
int main() {
    int N; string S; cin >> N >> S;

    for (auto c : S) num[c - 'a']++;
    long long res = 1;
    for (int i = 0; i < 26; ++i) {
        res *= num[i] + 1;
        res %= MOD;
    }
    cout << (res + MOD - 1) % MOD << endl;
}