※ 引述《JonathanWang.bbs@ptt.csie.ntu.edu.tw (小尹)》之銘言：
> m
> Online Judge 501
Problem:
Find out the number of permutations of L,U with length N, s.t.
There must at least one "UUU" in each permutation.
e.g.
UUUL, LUUU, UUUU are all possible permutation with length 4
Solution
Let S[n] be number of such permutations with length n.
Thus, S[0] = S[1] = S[2] = 0, S[3] = 1.
A recursion is defined
S[n] = 2*S[n-1] + (2^(n-4) - S[n-4])
if a permutation, say X, with length n-1 already contains UUU, then
XU or XL are permutations containing UUU with length n
if a permutation, say YLUU, with length n-4 does not contains UUU, then
YLUUU is permutation containing UUU with length n.
Above are the only two cases, that generates n-length permutation.
--
※ Origin: My Elixir BBS <localhost> ◆ From: 10.112.28.213
※ X-Originator: ACMCLUB.board@future.tfwu.org
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
※ 編輯: somi 來自: 140.112.205.244 (12/12 22:57)