A - Colorful Subsequence(AGC031)

問題リンク

感想

愚直にやってTLEした。そこから「もとの文字列から順序を変えずにつなげたもの」をそのまま受け取ってしまい、元の配列の順番のまま数え上げる方法がわからず（というか面倒）になって集中力がつきてしまった。
ちなみに、今回も考察不足で「もとの文字列から順序を変えずにつなげたもの」は別に順序を気にしなくてもよいことがわかる。...マジでしっかり考えましょう。最近頭動いてない。
運動するとちょっとは脳機能あがるかな

解法

まず、文字列列挙するのはわかる。それで「もとの文字列から順序を変えずにつなげたもの」をそのまま受け取ると、入力の文字列のindexを考慮しながら実装するのだがTLEに。
そこでもう一つの条件である「すべて異なる文字からなるものの数」を求めるということに注目する。すると、元の文字列の順番を考慮しなくてもよいことが見えてくる（実際に私は見えなかったが）。

アルファベット毎に考える。"a"を考えると

文字列中に一つしか出現できない。
"abbbacccaa"という文字列があった場合。どの"a"を文字列中に表示させるかを考えればよい。表示する"a"が決まると自然と並び順も決まる。ここが見えなかった
非表示というパターンもあるので忘れずに。

以上を踏まえると、各アルファベット毎に数え上げて、その個数+１個（+１は選択しないパターン）をかけ合わせていけばよい。
そして、最後にすべて選択しないという空文字の場合を考慮し、-１してMODとって終了。

まとめの感想

文字列列挙。アルファベットが高々26通りなので、そういところに注力すると計算量落とせるのかなと思って解いていったが、結局解けずじまい。