{Algo}Google的一道排列组合题

[pongba]

Google的一道题目，看了一下，觉得值得一做（题目是05年的，做过的同学可以保持沉默:P）：

假设有这样一种字符串，它们的长度不大于 26 ，而且若一个这样的字符串其长度为 m ，则这个字符串必定由 a, b, c ... z 中的前 m 个字母构成，同时我们保证每个字母出现且仅出现一次。比方说某个字符串长度为 5 ，那么它一定是由 a, b, c, d, e 这 5 个字母构成，不会多一个也不会少一个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些字母也就确定了，唯一的区别就是这些字母的前后顺序而已。

现在我们用一个由大写字母 A 和 B 构成的序列来描述这类字符串里各个字母的前后顺序：

如果字母 b 在字母 a 的后面，那么序列的第一个字母就是 A （After），否则序列的第一个字母就是 B （Before）；
如果字母 c 在字母 b 的后面，那么序列的第二个字母就是 A ，否则就是 B；
如果字母 d 在字母 c 的后面，那么 …… 不用多说了吧？直到这个字符串的结束。

这规则甚是简单，不过有个问题就是同一个 AB 序列，可能有多个字符串都与之相符，比方说序列"ABA"，就有"acdb"、"cadb"等等好几种可能性。说的专业一点，这一个序列实际上对应了一个 字符串集合。那么现在问题来了：给你一个这样的 AB 序列，问你究竟有多少个不同的字符串能够与之相符？或者说这个序列对应的字符串集合有多大？注意，只要求个数，不要求枚举所有的字符串。

据Elminster说，15分钟能够做出来就能够通过他老板的算法考试了:P

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[liuxinyu]

没有细想，说个思路，不一定对，欢迎指正。

把AB串分成如下n组：{AA...A}{BB...B}{AA...A}...
也就是连续的A或者B合并成一组。当然，一开始不一定是A了，也可能是B，不过没有关系。
针对每组内的字母顺序是固定死的，例如AAABBA...
则，a,b,c,d被第1组的3个A固定死了，顺序为abcd，
d,e,f被第2组2的个B固定死了，顺序为fed，
f,g被第3组的1个A固定死了，顺序为fg
...
现在把这n个串，保持原串内顺序，进行合并，合并的方案总数就是答案。

假设第一组有x1个元素，由于第2组的第一个元素（针对上例，就是d)是第一组的末尾，所以把第2组的第2元素（针对上例，就是e)，插入到x1个元素
的组中，有x1种方案，然后插如第2组的第3个元素（针对上例，就是f)，有1+2+3+...+x1种方案（分别针对第2元素插入第1个位置，第2个
位置...第x1个位置），下面插入第2组中的第4个元素，仍然只有1+2+3+...+x1种方案。

下面插入第3组第2个元素，假设第二组共有x2个元素，则第1第2组合并后，共有x1+x2个元素。同上面的分析可知，这时合并方案共有：
(1+2+3+...+x1)+(1+2+3+...+(x1+x2))种

所以针对形如{AA...x1个...A}{BB....x2个...B}...{XX...xn...X}{...}个的串，共有方案：
(1+2+...(x1)+(1+2+...(x1+x2))+...(1+2+...+(x1+x2+..xn))个方案

看看有没有错误？

[Ray Stinger]

已经做出来了，但我不知道为什么这是对的。我是凑数字凑的。

gques str = count str 1
where
len = length str
count [] _ = 1
count ('A':cs) n =
sum $ map (count cs) [1..n]
count ('B':cs) n =
sum $ map (count cs) [1..len-n+1]

第一步和最后一步都可以加速一下，但那样缺乏美感。动态规划，有空再说。

--
Ray Stinger, nickname Lich_Ray
God is in his heaven, all's right with the world.
-------------------------------------------------
let focus = 'computing' in where:
http://lichray.javaeye.com
let focus = 'computing' in here:
http://let-in.blogspot.com

[Hongcheng Zhu]

动态规划。
每次插入字符a,b,c,...
状态为当前放置一个字符后，该字符前面有和后面各有x,y个字符的情况下，不同串的个数。

On 7月2日, 下午5时08分, pongba <pon...@gmail.com> wrote:
> Google的一道题目，看了一下，觉得值得一做（题目是05年的，做过的同学可以保持沉默:P）：
>
> 假设有这样一种字符串，它们的长度不大于 26 ，而且若一个这样的字符串其长度为 m ，则这个字符串必定由 a, b, c ... z 中的前 m
> 个字母构成，同时我们保证每个字母出现且仅出现一次。比方说某个字符串长度为 5 ，那么它一定是由 a, b, c, d, e 这 5
> 个字母构成，不会多一个也不会少一个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些字母也就确定了，唯一的区别就是这些字母的前后顺序而已。
>
> 现在我们用一个由大写字母 A 和 B 构成的序列来描述这类字符串里各个字母的前后顺序：
>
> 如果字母 b 在字母 a 的后面，那么序列的第一个字母就是 A （After），否则序列的第一个字母就是 B （Before）；
> 如果字母 c 在字母 b 的后面，那么序列的第二个字母就是 A ，否则就是 B；
> 如果字母 d 在字母 c 的后面，那么 …… 不用多说了吧？直到这个字符串的结束。
>
> 这规则甚是简单，不过有个问题就是同一个 AB
> 序列，可能有多个字符串都与之相符，比方说序列"ABA"，就有"acdb"、"cadb"等等好几种可能性。说的专业一点，这一个序列实际上对应了一个
> 字符串集合。那么现在问题来了：给你一个这样的 AB
> 序列，问你究竟有多少个不同的字符串能够与之相符？或者说这个序列对应的字符串集合有多大？注意，只要求个数，不要求枚举所有的字符串。
>

> *据Elminster说，15分钟能够做出来就能够通过他老板的算法考试了:P*
>
> --
> 刘未鹏(pongba)|C++的罗浮宫http://blog.csdn.net/pongba
> TopLanguagehttp://groups.google.com/group/pongba

[liuxinyu]

加个修正，{AA...A}{B}和{AA...A}{BB...}有个小区别
前者的方案数就是A的个数x1，后者的方案数才是(1+2+...+x1)
例如AB则答案数就是2，ABB答案就是1+2

所以(1+2+...(x1)|x1+(1+2+...(x1+x2))|x1+x2+...(1+2+...+(x1+x2+..xn))|
(x1+x2+...+xn)
其中若AB发生变化时，后续是多于一个取|前面的公式，否则去后面的公式。

把这个翻译成代码，复杂度应该是最低的。

[谷祖超]

DP不错，序列A...B和A...BAAA的数量是有关系的，我的想法就是把整个序列拆分成连续的相同部分{A}{B}{A}{B}等，然后用DP求解。

在 08-7-3，liuxinyu<liuxi...@gmail.com> 写道：

[Ray Stinger]

现在这个程序就能算任意长度的串了：

use strict;
use warnings;

use Memoize;
use List::Util qw(reduce sum);

sub gques {
my $str = shift;
our $len = length $str;

sub count {
my ($s, $n) = @_;

if ($s eq "") {
return 1;
}
my $c = substr $s, 0, 1;
if ($c eq 'A') {
sum(map { count ((substr $s, 1), $_) } (1..$n));
} elsif ($c eq 'B') {
sum(map { count ((substr $s, 1), $_) } (1..$len-$n+1));
}
}
memoize 'count';
count $str, 1;
}

我写这个程序80%都花在了查一个Bug上，这个Bug是重叠函数调用....少了两个括号。Bug的弱智程度真的和找出它需要的时间成正比....

DB<1> print 'Result: '.(gques "ABBABAABABABBABAABABBBAABA").';
Result: 3.1986296886995e+028

接下来更让我晕倒就是这个了...Perl居然不像Python一样直接支持大整数....

[Gohan]

我想了半天还没想出来。。没看懂DP的方法

On 7月2日, 下午5时08分, pongba <pon...@gmail.com> wrote:

> Google的一道题目，看了一下，觉得值得一做（题目是05年的，做过的同学可以保持沉默:P）：
>
> 假设有这样一种字符串，它们的长度不大于 26 ，而且若一个这样的字符串其长度为 m ，则这个字符串必定由 a, b, c ... z 中的前 m
> 个字母构成，同时我们保证每个字母出现且仅出现一次。比方说某个字符串长度为 5 ，那么它一定是由 a, b, c, d, e 这 5
> 个字母构成，不会多一个也不会少一个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些字母也就确定了，唯一的区别就是这些字母的前后顺序而已。
>
> 现在我们用一个由大写字母 A 和 B 构成的序列来描述这类字符串里各个字母的前后顺序：
>
> 如果字母 b 在字母 a 的后面，那么序列的第一个字母就是 A （After），否则序列的第一个字母就是 B （Before）；
> 如果字母 c 在字母 b 的后面，那么序列的第二个字母就是 A ，否则就是 B；
> 如果字母 d 在字母 c 的后面，那么 …… 不用多说了吧？直到这个字符串的结束。
>
> 这规则甚是简单，不过有个问题就是同一个 AB
> 序列，可能有多个字符串都与之相符，比方说序列"ABA"，就有"acdb"、"cadb"等等好几种可能性。说的专业一点，这一个序列实际上对应了一个
> 字符串集合。那么现在问题来了：给你一个这样的 AB
> 序列，问你究竟有多少个不同的字符串能够与之相符？或者说这个序列对应的字符串集合有多大？注意，只要求个数，不要求枚举所有的字符串。
>

[liuxinyu]

这个周末，在摆脱了繁重的工作之后，终于利用家庭生活的边角时间，比较严谨认真的给出了这道题目的解，由于今天又是工作日，我只好再次利用边角时间，陆
续给出本题的三种典型解法，并依次分析比较思路和算法复杂度。

1. 直观解法，穷举。
目的：为什么要不惜时间空间给出穷举解法？最大的目的就是作为正确性检验的手段。
在一个题目没有公认答案，或者没有显而易见的通项公式时，穷举是检验某一解法正确与否的最可信服方法。这就好比，某人开发了一个利用三维成像计算体积，
然后利用红外测量密度分布，最后使用限元计算获得重量的非接触磅秤，他可以在100米外测量出某人的体重。可是如何知道体重是否计算的正确性？有效的方
法就是利用一个普通磅秤，然后把测量结果进行比较。

穷举法的思路非常直观：
使用起来大致如下：
filter hasPattern "AABBBA" permutation [a,b,c,d,e,f,g]
我们对abcdefg进行全排列，然后找出符合"AABBBA"形式的所有排列结果，最后计算他的个数。

全排列的算法，我在前几天正好给出了：
permutation xs n r= if length xs <= n-r
then [[]]
else [x:ys | x <- xs, ys <- permutation (delete x xs) n r]

perm xs = permutation xs n n where n=length xs

这是个haskell的解法，比一般命令式的要简洁一下，具体解释请参考：http://www.cpper.com/c/t4857.html

然后是hasPattern这个判断函数，其实现如下：
order f s = at s x `f` at s (1+x) where
x = minimum s
at (y:ys) v = if v==y then 1 else 1 + at ys v

delete_min xs = filter (\x->not (x==minimum xs)) xs

hasPattern [] _ = True
hasPattern ('A':ps) s = order (<) s && hasPattern ps (delete_min s)
hasPattern ('B':ps) s = order (>) s && hasPattern ps (delete_min s)

hasPattern用来判断一个序列是否符合某个"AB"串，为了简单起见，我用整数1表示英文字母a,2代表b，...
hasPattern接受两个参数，一个pattern串，一个代表英文字母的数字串。
如果pattern中的第一字符是A，我们要保证英文串中，最小的字符在此小的字符前，并且除掉最小字符的剩余部分，也符合pattern。
是B的话，结果则相反。

检查最小字符在此小字符前后的函数式order，他找出最小字符的位置和此小字符的位置，然后比较他们位置的大小。比较直观，不再赘述。

删除最小字符的函数是delete_min，可以利用filter比较容易的实现。

此后就可以根据pattern枚举所有的串了，实现如下：
enumStr1 pattern = filter f (perm [1..(1+length pattern)]) where
f = hasPattern pattern

count1 = length.enumStr1

前一个函数枚举所有的串，后一个计算这样的串的个数。运行结果如下：
enumStr1 "AAABBA"
[[1,2,3,6,5,4,7],[1,2,3,6,5,7,4],[1,2,3,6,7,5,4],[1,2,6,3,5,4,7],
[1,2,6,3,5,7,4],[1,2,6,3,7,5,4],[1,2,6,5,3,4,7],[1,2,6,5,3,7,4],
[1,2,6,5,7,3,4],[1,2,6,7,3,5,4],[1,2,6,7,5,3,4],[1,6,2,3,5,4,7],
[1,6,2,3,5,7,4],[1,6,2,3,7,5,4],[1,6,2,5,3,4,7],[1,6,2,5,3,7,4],
[1,6,2,5,7,3,4],[1,6,2,7,3,5,4],[1,6,2,7,5,3,4],[1,6,5,2,3,7,4],
[1,6,5,2,7,3,4],[1,6,5,7,2,3,4],[1,6,7,2,3,5,4],[1,6,7,2,5,3,4],
[1,6,7,5,2,3,4],[6,1,2,3,5,4,7],[6,1,2,3,5,7,4],[6,1,2,3,7,5,4],
[6,1,2,5,3,4,7],[6,1,2,5,3,7,4],[6,1,2,5,7,3,4],[6,1,2,7,3,5,4],
[6,1,2,7,5,3,4],[6,1,5,2,3,4,7],[6,1,5,2,3,7,4],[6,1,5,2,7,3,4],
[6,1,5,7,2,3,4],[6,1,7,2,3,5,4],[6,1,7,2,5,3,4],[6,1,7,5,2,3,4],
[6,5,1,2,3,4,7],[6,5,1,2,3,7,4],[6,5,1,2,7,3,4],[6,5,1,7,2,3,4],
[6,5,7,1,2,3,4],[6,7,1,2,3,5,4],[6,7,1,2,5,3,4],[6,7,1,5,2,3,4],
[6,7,5,1,2,3,4]]

count1 "AAABBA"
50

运算速度还是很慢的，但是我们能确定其结果是正确的。

明天，我将介绍第二个解法——递归生成。其计算速度会明显提高，最后我再介绍通项解法，不用枚举而求出串的个数。

[liuxinyu]

昨天一天不在，继续介绍解法二，递归生成。

这个解法的思路非常直观，根据一个AB串，生成全部合法的英文串可以这样考虑：
假设已经根据长度为n的AB串的后n-1个AB，生成了全部英文串(包含b,c,...到第n+1个英文字母），现在要根据第1个AB，生成最终结
果。
如果第一字符是A，那么只要试图把a插入到现有结果中b的前面，就获得了全部方案；
如果第一字符是B，那么只要试图把a插入到现有结果中b的后面，就获得了全部方案；
如果现有结果是空，那么只有一个方案，就是a

这个算法直观翻译成代码就是：

enumStrR from [] = [[from]]

enumStrR from ('A':ps) = foldl (++) [] (map f (enumStrR (from+1) ps))
where
f = insert_before from
insert_before y (x:xs) = if x==y+1 then [y:x:xs]
else [y:x:xs]++ (map (x:)
(insert_before y xs))

enumStrR from ('B':ps) = foldl (++) [] (map f (enumStrR (from+1) ps))
where
f = insert_after from
insert_after y (x:xs) = if x==y+1 then map (x:) (insert_any y xs)
else map (x:) (insert_after y xs)
where
insert_any y [] = [[y]]
insert_any y (x:xs) = [y:x:xs]++
(map (x:) (insert_any y xs))

enumStr2 = enumStrR 1

可能比较复杂，略微解释一下。首先看最后一句，enumStr2 = enumStrR 1，这句很简单。枚举具备pattern为"AAABBA"的
所有英文串，可以这样调用：
enumStr2 "AAABBA"，实际上，就是“递归从1（也就是字母a）m枚举所有英文串的意思”，相当于enumStrR 1
"AAABBA"

如果pattern是空，那么结果就是[[from]]，也就是[[1]]
如果pattern不空，则取出第一字母，根据他是A或者B分别处理。
enumStrR (from+1) ps，是从a的后继字母(也就是from+1)b开始，根据除第一字母外剩余字母枚举所有的方案。
对这些方案集合中的每个元素应用（也就是map）insert_after或者insert_before，如果是A就insert_before，否
则insert_after
这样就会针对每个元素生成若干方案，把他们加到一起（利用foldl，初始值空集合和序列相加运算++），就是最终结果。

insert_before实现很简单：
insert_before y (x:xs) = if x==y+1 then [y:x:xs]
else [y:x:xs]++ (map (x:)
(insert_before y xs))
他的含义就是，如果待插入序列的首字符就是待插入字符的后继字符，（例如待插入字符为a，待插入序列为bcd的形式）。那么就仅有一种方案。（对应为
abcd），否则，就把这一方案（abcd)，和递归地把该字符向除去首字符的子串中insert_before的结果合并为最终结果。

insert_after稍微复杂一些：
insert_after y (x:xs) = if x==y+1 then map (x:) (insert_any y xs)
else map (x:) (insert_after y xs)
where
insert_any y [] = [[y]]
insert_any y (x:xs) = [y:x:xs]++
(map (x:) (insert_any y xs))
针对首字符为待插入字符后继字符的情况，我们可以把待插入字符通过insert_any插入到任意位置，反之。就要递归地寻找后继字符，并完成插
入。insert_any的实现极为简单，这里不再赘述。

枚举所有方案后，获得方案数目就非常简单了：
count2 = length.enumStr2

现在，就可以检验这一方法的正确性，可以通过和方法1的结果对比：
EnumStr> enumStr2 "AAABBA"
[[1,2,3,6,5,4,7],[1,2,6,3,5,4,7],[1,6,2,3,5,4,7],[6,1,2,3,5,4,7],
[1,2,6,5,3,4,7],[1,6,2,5,3,4,7],[6,1,2,5,3,4,7],[1,6,5,2,3,4,7],
[6,1,5,2,3,4,7],[6,5,1,2,3,4,7],[1,2,3,6,5,7,4],[1,2,6,3,5,7,4],
[1,6,2,3,5,7,4],[6,1,2,3,5,7,4],[1,2,6,5,3,7,4],[1,6,2,5,3,7,4],
[6,1,2,5,3,7,4],[1,6,5,2,3,7,4],[6,1,5,2,3,7,4],[6,5,1,2,3,7,4],
[1,2,6,5,7,3,4],[1,6,2,5,7,3,4],[6,1,2,5,7,3,4],[1,6,5,2,7,3,4],
[6,1,5,2,7,3,4],[6,5,1,2,7,3,4],[1,6,5,7,2,3,4],[6,1,5,7,2,3,4],
[6,5,1,7,2,3,4],[6,5,7,1,2,3,4],[1,2,3,6,7,5,4],[1,2,6,3,7,5,4],
[1,6,2,3,7,5,4],[6,1,2,3,7,5,4],[1,2,6,7,3,5,4],[1,6,2,7,3,5,4],
[6,1,2,7,3,5,4],[1,6,7,2,3,5,4],[6,1,7,2,3,5,4],[6,7,1,2,3,5,4],
[1,2,6,7,5,3,4],[1,6,2,7,5,3,4],[6,1,2,7,5,3,4],[1,6,7,2,5,3,4],
[6,1,7,2,5,3,4],[6,7,1,2,5,3,4],[1,6,7,5,2,3,4],[6,1,7,5,2,3,4],
[6,7,1,5,2,3,4],[6,7,5,1,2,3,4]]
EnumStr> count2 "AAABBA"
50
EnumStr> count1 "AAB" == count2 "AAB"
True
EnumStr> count1 "AABB" == count2 "AABB"
True
EnumStr> count1 "AABBB" == count2 "AABBB"
True
EnumStr> count1 "A" == count2 "A"
True
EnumStr> count1 "AA" == count2 "AA"
True
EnumStr> count1 "ABA" == count2 "ABA"
True

明天我将介绍第三个解法，不需要枚举所有方案，使用类似通项公式的方法来解此问题，并对比三种方法的复杂度。

[liuxinyu]

为了方便普及，我后继会把所有解法翻译为C++的。不过要看我的空余时间了

[liuxinyu]

明天组织人team building，这个周末都不在，所以先抽空把第三种方法的代码贴上。

patternToN (x:xs) = p2N x xs where
p2N from [] = [1]
p2N from (x:xs) = if from == x then (1 + head next):tail next else
1:(p2N x xs) where
next = p2N x xs

countN (n:ns) = if ns == [] then 1 else sumTo (n+1) n2 (n+n2) (tail
ns) where
n2=head ns
--sumTo m deep accu ns
sumTo m 1 accu [] = m
sumTo m 1 accu (i:is) = sum (map (\x->sumTo x i (accu+i) is)
[accu+1-m+1..accu+1])
sumTo m deep accu ns = sum (map (\x->sumTo x (deep-1) accu ns)
[1..m])

count3 ps = countN (patternToN ps)

运行结果如下：
EnumStr> count3 "AAABBA"
50
EnumStr> count3 "AAB"
3
EnumStr> count3 "AABB"
6
EnumStr> count3 "AAABBA"
50
EnumStr> count3 "AAB" == count2 "AAB"
True
EnumStr> count3 "AABB" == count2 "AABB"
True
EnumStr> count3 "AABBB" == count2 "AABBB"
True
EnumStr> count3 "AA" == count2 "AA"
True
EnumStr> count3 "AABBAAA" == count2 "AABBAAA"
True

这一方法的思路基本如我最早回复，但是仔细分析后，加入了一些修正。这到题目，不用计算机，完全可以手工给出答案的公式。我下周抽时间给出这一公式的思
路和分析。

[bender]

不知道这个算式对不对
(length + 1)! / 2^length

[Alecs King]

On Wed, Jul 02, 2008 at 05:08:33PM +0800, pongba wrote:
> 那么现在问题来了：给你一个这样的 AB
> 序列，问你究竟有多少个不同的字符串能够与之相符？

get ab = sum $ foldl f [1] ab
where f last 'A' = scanl (+) 0 last
f last 'B' = scanr (+) 0 last

--
Alecs King

[Lich_Ray]

这仍然是直接生成的方法。不过我也很郁闷，因为我用聪明一点的方法做错了...

[Lich_Ray]

我觉得我特好玩儿，因为受到了楼上如此简短的代码的刺激，1分钟就把我自己的算法改对了 :)

gques str = count str 1
where

len = length str + 1

count [] _ = 1
count ('A':cs) n =

sum $ map (count cs) [n+1..len-length cs]

count ('B':cs) n =

sum $ map (count cs) [1..n]

那个 Perl 的加记忆的版本就不发了，没意思。我们期待手动计算的人。

[Lich_Ray]

On Thu, 10 Jul 2008 16:41:48 +0800
Alecs King <al...@perlchina.org> wrote:

这个很快啊，是怎么想到的能说明一下吗？

[liuxinyu]

现在说下第3种方法的思路。我们从一个例子AAB开始
如前面我分析的AA已经决定了abc的先后顺序，现在B字母决定了d必然在c的前面。
所以d可以放置的位置如下:
_1_ a _2_ b _3_ c
也就是d可以放在1,2,3任何一个位置。因此我们对于形如AAA...AB(n个A)的串（对BBB...BA亦然）的个数可以确定为n+1

下面考虑AABB，增加了一个B后，我们需要在d的前面放置e，我们依次展开防止d时的3种分支

_1_: 对于把d放置在这个位置，我们只有一个选择，把e放置在d的前面；
_2_: 对于把d放置在这个位置，我们有2个选择：_1_ a _2_ d b c；
_3_: 对于吧d放置在这个位置，我们有3个选择：_1_ a _2_ b _3_ d c；

规律是，当把前一个字母放在第i个位置时，我们有i个子方案，写成树状结构如下：

3
1, 2, 3

我们在考虑串AABBB，依照上述分析，总方案树如下：
3
1, 2, 3
1, 1, 2 1,2,3

对应AABBBB的方案树为：
3
1, 2, 3
1, 1, 2, 1, 2, 3
1, 1, 1, 2 1, 1, 2 1,2,3

是不是像分形？每次把叶子节点的值加起来就是最终结果。

现在考虑AAABBA我们可以很轻松写出前面3个A和2个B的树形方案：
4
1 2 3 4
现在问题来了，根据地5个A, 字母g要放在f的后面。而放置字母f的方案总数为1+2+3+4分别对应放在最左，最左或左数第2，最左或左数第2或第
3....
所以对应f放在最左，有6种放置g的方案，分别放在左数第2到第7
对应f放在左数第2，有5种放置g的方案，分别对应放在左数低3到低7
...
因此AAABBA的方案树为：
4
1 2 3 4
6 6 5 6 5 4 6 5 4 3

现在考虑AAABBAA，我们可以用前面同样的思路，给出方案数为：
4
1 2 3 4
6 6 5 6 5 4 6 5 4 3
1..6 1..6 1..5 1..6 1..5 1..4 1..6 1..5 1..4 1..3

我想现在规律已经出来了：
对于形如AA.n1个..ABB..n2个.BAA..n3个.A....BB.np个..B的AB串，我们只要把方案数画出来，然后计算最后一行的数
字和就可以了。
数根的值为n1+1，然后第1层为1到n1+1，然后从该层每个值为i的节点，分支出1..i的子树，重复下去，直到n2层
然后第n3层从每个值为i的节点，分支出(n1+n2+n3)-i+2..(n1+n2+n3+1)的子树。