Solution to http://11011110.livejournal.com/254164.html

require 'set'
def _distinct_subsequences(s_prime, k_prime, cache)
  if cache.key? [s_prime, k_prime]
    return cache[[s_prime, k_prime]]
  end
  chars = s_prime.split('')
  if k_prime > chars.length
    return 0
  elsif k_prime == chars.length
    return 1
  elsif k_prime == 1
    result = chars.uniq.length
  else
    seen = Set.new
    result = 0
    chars.each_with_index do |c, i|
      next if seen.include?(c)
      seen << c
      to_the_right = s_prime.slice(i+1..-1)
      result += _distinct_subsequences(to_the_right, k_prime-1, cache)
    end
  end
  cache[[s_prime, k_prime]] = result
  return result
end

def distinct_subsequences(s, k)
  cache = {}
  result = _distinct_subsequences(s, k, cache)
  return result
end

distinct_subsequences('food', 2) == 4
distinct_subsequences('10'*100, 100) == 2**100