# AtCoder Grand Contest 031

URL: https://atcoder.jp/contests/agc031 (opens new window)

# A

全部異なる文字なら 2^n - 1 という事実をを応用する。この式はそれぞれの文字について「取る」「取らない」の2通りあるから 2^n で全部取らない方法を除くから -1 することを表している。

重複する文字cがある場合 「cのいずれか1個を取る」「どれも取らない」のc+1通りあるから c+1を文字ごとに求めて積を取って最後に-1する。

n = gets.chomp.to_i
s = gets.chomp

hash = {}
s.each_char do |c|
  hash[c] ||= 1
  hash[c] += 1
end

MAX = 10 ** 9 + 7
count = 1
hash.each do |k, v|
  count *= v
  count %= MAX
end

puts count - 1
Last Updated: 2020/08/09 18:33