tt259566.clj

(def cs [:a :b :c])

(defn ^:dynamic S [k]
  (if-let [key (get cs (dec k))]
    (assoc (zipmap cs (repeat 0)) key 1 :n 1)
    (let [children (map S (range (- k 3) k))]
      (-> (apply merge-with + (map #(dissoc % :children) children))
          (assoc :children children)))))

(defn solve* [t s e acc]
  (if-let [children (:children t)]
    (loop [i 0, [{:keys [n] :as child} & more] children, acc acc]
      (if child
        (let [i' (+ i n)]
          (cond (<= i' s) (recur i' more acc)
                (< i e)
                (let [s' (max 0 (- s i)), e' (min n (- e i))]
                  (if (and (= s' 0) (= e' n))
                    (recur i' more (merge-with + acc (dissoc child :n :children)))
                    (recur i' more (solve* child s' e' acc))))
                :else acc))
        acc))
    (merge-with + acc (dissoc t :n))))

(defn solve [n s e]
  (binding [S (memoize S)]
    (solve* (S n) (dec s) e {})))
    
(comment

  (solve 2 1 1)
  ;=> {:a 0, :b 1, :c 0}
  
  (solve 4 1 3)
  ;=> {:a 1, :b 1, :c 1}
  
  (solve 5 1 5)
  ;=> {:a 1, :b 2, :c 2}
  
  (solve 42 1366704551 15256729588)
  ;=> {:a 3169085520, :b 4892082497, :c 5828857021}

  )