SRM 330 div1 level2

TrieもしくはPrefixed Treeなるものがあるらしいが。

要するに

• ある要素があるPrefix-Freeの集合体のどの要素のPrefixでもないならば、集合和もPrefix-Free
• ある要素をSubset数Sの集団に加えた時、Subset数は２Sになる（元のSubsetと新要素＋各Subsetでできる新Subsetの和だから）
• 文字列をソートすれば、PrefixとそれをPrefixにもつ全要素が連続する。
  a, ab, ac, d, ddであればab, acがaをprefixにもつ。
• 文字列をソートして、降順に「Prefix-Freeの要素数」を数えてメモライズすればよい
  　新Subset数＝旧Subset数＋新要素がPrefixとならない全旧Subset数
  なので、降順からループした時、
  　値　＝　前回の値　＋ 新要素がPrefixとならない単語まで遡った所の値
  　　　　　　　　　　　　　　　（それ以前の全要素とはPrefix-Freeとなるため）
  で求められる。

DPのmemが直接戻り値になる理論で考えれば自然にたどり着く・・・