Colorful Subsequence - AtCoder Grand Contest 031 A

AGC031-A, 200点でした。
問題リンク

解説

重要な点として、

• 部分列は全て異なる文字からならねばならない
• 文字列として同一でも、異なる位置から取り出された部分列は区別して数える

ということがあります。
僕は問題文の勘違いもあってかなり迷走しましたが、結局、

• 各アルファベットは1回しか現れられない
• 異なる位置にある同じアルファベットを選んだ文字列同士は区別して数えられる

ので、
例えば'a'が中に回現れたとすると、'a'については

• 部分列に一つも含まれない
• 部分列に番目の'a'が含まれる

ので、'a'の選び方はパターンあるわけです。

各アルファベットについて、(その個数+1の積)-1が答えになります。
(最後に-1する理由ですが、この方法だと全てのアルファベットが一つも部分列に含まれない場合、つまりからの文字列となる場合を1つだけ含むからです。)

▶ソースコードを開く

const long MOD = 1000000007;

long n;
std::string s;
long ans = 1;
long alp[26];
 
int main(){
	scanf("%ld", &n);
	std::cin >> s;
	for(int i = 0; i < n; i++){
		alp[s[i] - 'a']++;
		alp[s[i] - 'a'] %= MOD;
	}
	for(int i = 0; i < 26; i++){
		ans *= (alp[i]+1);
		ans %= MOD;
	}
	printf("%ld\n", ans-1);
	return 0;
}