正直、「解説」は一体何を言いたいのかよくわからないですね。内容が理解できるまでは一旦無視した方が良いでしょう。
まず、出題中の出力例1(全ての文字が異なる場合)では、2^N-1 (^
はXORではなく、べき乗)で与えられることは理解できるでしょうか。
例の場合、N=4ですから、2^4-1=15 が答えとなります。
この考え方ですが、
この出題における「部分列」(通常のよく使われる意味の「部分列」とは異なります)は、
a,b,ab,c,ac,bc,abc,d,ad,bd,abd,cd,acd,bcd,abcd
の15通りがあるわけですが、この15通りを実際に作らなくても、考え方がわかれば数だけは出せるわけです。
a (a使う , b使わない, c使わない, d使わない)
b (a使わない, b使う , c使わない, d使わない)
ab (a使う , b使う , c使わない, d使わない)
c (a使わない, b使わない, c使う , d使わない)
a c (a使う , b使わない, c使う , d使わない)
bc (a使わない, b使う , c使う , d使わない)
abc (a使う , b使う , c使う , d使わない)
d (a使わない, b使わない, c使わない, d使う )
a d (a使う , b使わない, c使わない, d使う )
b d (a使わない, b使う , c使わない, d使う )
ab d (a使う , b使う , c使わない, d使う )
cd (a使わない, b使わない, c使う , d使う )
a cd (a使う , b使わない, c使う , d使う )
bcd (a使わない, b使う , c使う , d使う )
abcd (a使う , b使う , c使う , d使う )
-------------------------------------------
(a使わない, b使わない, c使わない, d使わない) この出題の「部分列」の定義に当てはまらない
a,b,c,d それぞれの文字について(使う, 使わない)の2通りの選択があって、それが4文字ですから、総数は、2×2×2×2=16通り。ただ、それだと全部「使わない」が含まれてしまっているので、1を引いて15通りとなるわけです。
こう考えれば、どのアルファベットを使っているかは関係なく、文字の種類が何種類あるかを表す N だけわかれば、総数は計算できるということはご理解いただけるでしょうか。
出題中の出力例2を見てみます。
入力文字列 baa に対しては、
b,a(1個目のa),a(2個目のa),ba(1個目のa),ba(2個目のa)
の5通りあるので、5 という答えが出せないといけません。
これを上と同じようにみて行くとこんな感じになります。
b (b使う , a使わない )
a (b使わない, a1個目使う)
a (b使わない, a2個目使う)
ba (b使う , a1個目使う)
b a (b使う , a2個目使う)
------------------------
(b使わない,a使わない ) この出題の「部分列」の定義に当てはまらない
と見ることができます。1回しか現れない文字 b については、(使う, 使わない)の2通り、2個現れる a については、(1個目使う, 2個目使う, 使わない)の3通りで、総数は 2×3=6通り、両方「使わない」は上と同様に除かないといけないので、1を引いて 5 と計算できることになります。
同じように出題中の出力例3を考えると、文字列が abcab ですから、aが2個、bが2個、cが1個ですから、aについて(1個目使う, 2個目使う, 使わない)の3通り、bについても同じく3通り、cについては(使う, 使わない)の2通り、で総数の3×3×2=18から、全部「使わない」の1を引いて、17 が答えになります。
つまり、ある文字の出現回数がわかれば、その(出現回数+1)が、その文字に関する場合の数を表しているということになります。
全く現れない文字については、(使わない)の一択なので配列c[]
の値を1にしておけば、×1は何もしないのと一緒なのでうまい具合に無視してくれるので、場合分けなどせずにc[]
の全要素を掛け算すれば良いことになります。
あなたの見たコードのint
配列c[]
は、全要素の初期値が1にしてあるか、数え終わった後に全要素に1を足す、ということをしているのではないでしょうか。
ご理解いただけたでしょうか。わかりにくい部分があれば、どの部分がどうわからないかを具体的に知らせていただければ、もう少し詳しく書けるところがあるかもしれません。