Documentation
¶
Overview ¶
T(i, j) 投完前 i 个硬币，j 个 head 的概率 T(1, 0) = 1 - p_1 T(1, 1) = p_1
T(i, j) = T(i-1, j) * (1_p_j) + T(i-1, j-1) * p_j
T(i, j) 前 i 个小朋友消费了 j 个糖果的方案数 则 T(n, k) 为最终答案
T(i, j) = Sum{T(i-1, j) + T(i-1, j-1) + ... + T(i-1, j-a[i]) } = rangeSum([j-a[i], j]) = rangeSum([j-a[i], j+1))
T(i, d) 表示范围为 [1, i] 的结尾为 d 的排列数 0 <= i <= n, 1 <= d <= i 则 Sum{ T(n, d) } 为最终解
T(i, d) = if s[i-1] = '<'，则 d 要大于 T(i-1) 的结尾数字，Sum{ T(i-1, d') } 1 <= d' < d if s[i-1] = '>'，则 d 要小于 T(i-1) 的结尾数字，Sum{ T(i-1, d') } d <= d' <= i-1
考虑 T(3, x) 的合法情况，假设 seq = <>< T(3, 1) = {[2, 3, 1]} T(3, 2) = {[1, 3, 2]} T(3, 3) = {}
构造 T(4, x) 的过程如下，因为 seq[2] = '<' T(4, 1) = 以 1 结尾没有任何 T(3, x) 的结尾满足 < 代表的升尾条件，故 0 T(4, 2) = T(3, 1) = 1 注：T(3, 1) 的唯一答案为：[2, 3, 1] = 因为新序列以 2 结尾，将原序列 >= 2 的数字+1，构成新序列 => [3, 4, 1] = append 2 作为结尾 => [3, 4, 1, 2] T(4, 3) = T(3, 1) + T(3, 2) T(4, 4) = T(3, 1) + T(3, 2) + T(3, 3)
如果 seq[2] = '>' 呢？ T(4, 1) = T(3, 1) + T(3, 2) + T(3, 3) 注意：以 1 结尾的排列做变换后为 2，故 > 1 T(4, 2) = T(3, 2) + T(3, 3) T(4, 3) = T(3, 3) T(4, 4) = 0
Source Files