重排物品

iseemu2009

重排物品问题

mathe

其实一条横杠就是代表一次交换操作，我们可以一次交换前两个数(S)，也可以交换后两个数(T)。
而三个物体最多6个排列顺序，如
ABC ACB BAC BCA CAB CBA
我们假设第一种S交换u个，第二种T交换v个可以达到这6种排序的数目分别为
ABC(u,v),ACB(u,v),BAC(u,v),BCA(u,v),CAB(u,v),CBA(u,v)
由于连续两次S交换会回复原先状态，连续两次T交换也会回复原先状态
对任意长度为u+v的S,T序列，我们可以先消除相邻的偶数个S和相邻的偶数个T为一次变换，而且只要可能总是从左到右进行合并
于是我们可以通过多次变换将序列变换为
STST...ST
STST...STS
TSTS...TS
TSTS...TST
四种类型之一。
由于STSTST和TSTSTS都又总是回复原始状态，而且检验可以知道，变换
S,ST,STS,STST,STSTS, T,TS,TST,TSTS,TSTST 都无法将ABC变换会原始状态，
所以我们需要计数所有经过上面多次变换变化为\((ST)^{3k}\)或\((TS)^{3k}\)个状态的初始序列数目(初始序列中有u个S和v个T)

然后我们先计算包含2m个S以及2n个T可以通过前面相邻合并操作变成空串的序列数目a(2m,2n), 和逐步合并过程中，最前面永远不会出现单个T的数目为b(2m,2n)，
比如TT就不允许，应该T开头，同样SSTSST也不允许，第一步从左到右合并到两个S以后变成TSST就以T开头了。同样合并过程前面永远不会出现当个S的数目为c(2m,2n)=b(2n,2m).
有了这个初始结果后，就可以对上面的计数过程对k进行分类，
对于每个给定的k,将余下可用的S和T分配到它们之间的6k+1个空格之中，每个空格中的S和T都必须偶数个。这样就可以对每个空格中可用方案数目使用数组a，b进行计算了。
其中第一个空格用数组a计数，后面空格分别根据它前面位置是T还是S分别采用b(2m,2n)和c(2m,2n)=b(2n,2m)来进行计数。而且需要注意到所有以S开头的空格之间使用的模式相互交换结果是相同的，所以所有S开头的空格填充的模式之间可以再次使用组合数来简化，同样T开头的空格也类似。
通过这种方法，就应该可以极大降低计算量。