阿弥陀签-ProjectEuler 837
重排物品问题 其实一条横杠就是代表一次交换操作，我们可以一次交换前两个数(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开头的空格也类似。
通过这种方法，就应该可以极大降低计算量。
这个题目计算的空间复杂度还是有些大。
对于上面的S,T序列，由于\(S^2,T^2,(ST)^3,(TS)^3\)都等价于没有变换，所以最终每个序列可以变换为下面11种状态之一
E: 等于无变换状态，也就是我们需要计数的最终状态
S, T, ST, TS, STS, TST, STST, TSTS, STSTS, TSTST.
但是上面总共11个状态，对于11阶群，显然有问题，经过计算发现STS=TST,我们可以记为状态F,于是最终只有6个状态
E，S, T, ST, TS, F=STS=TST
比如FS=STSS=ST, FT=TSTT=TS, SF=SSTS=TS, TF=TTST=ST
于是我们可以记\(f_E(u,v),f_S(u,v),f_T(u,v),f_{ST}(u,v),f_{TS}(u,v), f_F(u,v)\)分别代表包含u个S,v个T的序列最终等价状态分别为这六种时的数目。
很显然\(f_E(u,v)+f_S(u,v)+f_T(u,v)+f_{ST}(u,v)+f_{TS}(u,v)+f_F(u,v)=C_{u+v}^u\).
另外根据T,S的对称关系，可以有\(f_E(u,v)=f_E(v,u), f_S(u,v)=f_T(v,u), f_{ST}(u,v)=f_{TS}(v,u), f_F(u,v)=f_F(v,u)\).
而如果将每个序列去掉第一个字母或最后一个字母，就很容易得到基本递推关系
\(\begin{cases}
f_E(u,v)=f_S(u-1,v)+f_T(u,v-1)\\
f_S(u,v)=f_E(u-1,v)+f_{TS}(u,v-1)=f_E(u-1,v)+f_{ST}(u,v-1) \\
f_T(u,v)=f_E(u,v-1)+f_{TS}(u-1,v)=f_E(u,v-1)+f_{ST}(u-1,v)\\
f_{ST}(u,v) = f_T(u-1,v)+f_F(u,v-1)=f_S(u,v-1)+f_F(u-1,v)\\
f_{TS}(u,v) = f_S(u,v-1)+f_F(u-1,v)=f_T(u-1,v)+f_F(u,v-1)\\
f_F(u,v)=f_{TS}(u-1,v)+f_{ST}(u,v-1)=f_{TS}(u,v-1)+f_{ST}(u-1,v)
\end{cases}
\)
所以根据上面递推式还可以得出\(f_{ST}(u,v)=f_{TS}(u,v)\)
初始状态为\(f_{*}(u,-1)=f_{*}(-1,v)=0, f_E(0,0)=1,f_S(0,0)=f_T(0,0)=f_{ST}(0,0)=f_{TS}(0,0)=f_F(0,0)=0\) 利用上面方案可以计算出如下10以内的表格，其中E代表题目中f(i,j),看上去应该没有问题。
但是使用这种方法计算出来f(321,123)%1234567891应该是847981364，和题目中给定数据不匹配
E=0
S=1
T=0
ST=TS=0
F=0
E=0
S=0
T=0
ST=TS=1
F=0
E=1
S=0
T=0
ST=TS=0
F=0
E=0
S=0
T=2
ST=TS=0
F=1
E=4
S=0
T=0
ST=TS=1
F=0
E=0
S=1
T=0
ST=TS=0
F=0
E=0
S=0
T=0
ST=TS=2
F=0
E=0
S=4
T=1
ST=TS=0
F=3
E=2
S=0
T=0
ST=TS=7
F=0
E=1
S=0
T=0
ST=TS=0
F=0
E=0
S=0
T=3
ST=TS=0
F=2
E=7
S=0
T=0
ST=TS=3
F=0
E=0
S=2
T=14
ST=TS=0
F=10
E=28
S=0
T=0
ST=TS=12
F=0
E=0
S=1
T=0
ST=TS=0
F=0
E=0
S=0
T=0
ST=TS=3
F=0
E=0
S=7
T=3
ST=TS=0
F=6
E=5
S=0
T=0
ST=TS=20
F=0
E=0
S=28
T=17
ST=TS=0
F=32
E=34
S=0
T=0
ST=TS=60
F=0
E=1
S=0
T=0
ST=TS=0
F=0
E=0
S=0
T=4
ST=TS=0
F=3
E=11
S=0
T=0
ST=TS=6
F=0
E=0
S=5
T=31
ST=TS=0
F=26
E=59
S=0
T=0
ST=TS=43
F=0
E=0
S=34
T=119
ST=TS=0
F=103
E=238
S=0
T=0
ST=TS=137
F=0
E=0
S=1
T=0
ST=TS=0
F=0
E=0
S=0
T=0
ST=TS=4
F=0
E=0
S=11
T=6
ST=TS=0
F=10
E=11
S=0
T=0
ST=TS=41
F=0
E=0
S=59
T=54
ST=TS=0
F=84
E=88
S=0
T=0
ST=TS=203
F=0
E=0
S=238
T=225
ST=TS=0
F=340
E=450
S=0
T=0
ST=TS=578
F=0
E=1
S=0
T=0
ST=TS=0
F=0
E=0
S=0
T=5
ST=TS=0
F=4
E=16
S=0
T=0
ST=TS=10
F=0
E=0
S=11
T=57
ST=TS=0
F=51
E=116
S=0
T=0
ST=TS=105
F=0
E=0
S=88
T=319
ST=TS=0
F=308
E=557
S=0
T=0
ST=TS=533
F=0
E=0
S=450
T=1135
ST=TS=0
F=1111
E=2270
S=0
T=0
ST=TS=1561
F=0
E=0
S=1
T=0
ST=TS=0
F=0
E=0
S=0
T=0
ST=TS=5
F=0
E=0
S=16
T=10
ST=TS=0
F=15
E=21
S=0
T=0
ST=TS=72
F=0
E=0
S=116
T=126
ST=TS=0
F=177
E=214
S=0
T=0
ST=TS=496
F=0
E=0
S=557
T=747
ST=TS=0
F=1029
E=1197
S=0
T=0
ST=TS=2164
F=0
E=0
S=2270
T=2758
ST=TS=0
F=3725
E=5516
S=0
T=0
ST=TS=5995
F=0
E=1
S=0
T=0
ST=TS=0
F=0
E=0
S=0
T=6
ST=TS=0
F=5
E=22
S=0
T=0
ST=TS=15
F=0
E=0
S=21
T=94
ST=TS=0
F=87
E=210
S=0
T=0
ST=TS=213
F=0
E=0
S=214
T=706
ST=TS=0
F=709
E=1263
S=0
T=0
ST=TS=1456
F=0
E=0
S=1197
T=3427
ST=TS=0
F=3620
E=5697
S=0
T=0
ST=TS=6378
F=0
E=0
S=5516
T=11692
ST=TS=0
F=12373
E=23384
S=0
T=0
ST=TS=17889
F=0
调出bug了，公式抄错了一个地方。
现在主要问题是复杂度太高，
比如f(123,321)可以0.002s得出172633303
f(12345,54321)需要4.618s得出232961944.
现在验证了公式
\(\begin{cases}
f_E(u,v)=f_S(u-1,v)+f_T(u,v-1)\\
f_S(u,v)=f_E(u-1,v)+f_{TS}(u,v-1)=f_E(u-1,v)+f_{ST}(u,v-1) \\
f_T(u,v)=f_E(u,v-1)+f_{TS}(u-1,v)=f_E(u,v-1)+f_{ST}(u-1,v)\\
f_{ST}(u,v) = f_T(u-1,v)+f_F(u,v-1)=f_S(u,v-1)+f_F(u-1,v)\\
f_{TS}(u,v) = f_S(u,v-1)+f_F(u-1,v)=f_T(u-1,v)+f_F(u,v-1)\\
f_F(u,v)=f_{TS}(u-1,v)+f_{ST}(u,v-1)=f_{TS}(u,v-1)+f_{ST}(u-1,v)
\end{cases}
\)
的正确性，我们看看能否有更好解决这个问题的方案。上面用下标写法太麻烦了，修改一下，直接用下标代替函数本省, 也就是写成递推式
\(\begin{cases}
E(u,v)=S(u-1,v)+T(u,v-1)\\
S(u,v)=E(u-1,v)+TS(u,v-1)=E(u-1,v)+ST(u,v-1) \\
T(u,v)=E(u,v-1)+TS(u-1,v)=E(u,v-1)+ST(u-1,v)\\
ST(u,v) = T(u-1,v)+F(u,v-1)=S(u,v-1)+F(u-1,v)\\
TS(u,v) = S(u,v-1)+F(u-1,v)=T(u-1,v)+F(u,v-1)\\
F(u,v)=TS(u-1,v)+ST(u,v-1)=TS(u,v-1)+ST(u-1,v)
\end{cases}
\)
然后我们直到对于没有S的情况，也就是u=0的情况，当v是偶数时，状态是E,当v是奇数时，状态时T,所以我们得到
\(\begin{cases}E(0,v)=\frac{1+(-1)^v}2\\S(0,v)=0\\T(0,v)=\frac{1-(-1)^v}2\\ST(0,v)=TS(0,v)=0\\F(0,v)=0\end{cases}\)
另外对递推公式，我们可以继续迭代一次，得到
\(\begin{cases}
E(u,v)=S(u-1,v)+T(u,v-1)=S(u-1,v)+TS(u-1,v-1)+E(u,v-2)\\
S(u,v)=E(u-1,v)+TS(u,v-1)=E(u-1,v)+F(u-1,v-1)+S(u,v-2) \\
T(u,v)=TS(u-1,v)+E(u,v-1)=TS(u-1,v)+S(u-1,v-1)+T(u,v-2)\\
TS(u,v) = F(u-1,v)+S(u,v-1)=F(u-1,v)+E(u-1,v-1)+TS(u,v-2)\\
F(u,v)=TS(u-1,v)+TS(u,v-1)=TS(u-1,v)+F(u-1,v-1)+S(u,v-2)
\end{cases}
\)
前面4个都很不错，就是第五个比较麻烦，我们可以将第5个改写为
\(F(u,v)=S(u,v)-E(u-1,v)+TS(u-1,v)\)
现在如果我们将u=1,代入，可以得到
\(\begin{cases}
E(1,v)=S(0,v)+TS(0,v-1)+E(1,v-2)\\
S(1,v)=E(0,v)+F(0,v-1)+S(1,v-2) \\
T(1,v)=TS(0,v)+S(0,v-1)+T(1,v-2)\\
TS(1,v) =F(0,v)+E(0,v-1)+TS(1,v-2)\\
F(1,v)=S(1,v)-E(0,v)+TS(0,v)
\end{cases}
\)
\(\begin{cases}E(0,v)=\frac{1+(-1)^v}2\\S(0,v)=0\\T(0,v)=\frac{1-(-1)^v}2\\ST(0,v)=TS(0,v)=0\\F(0,v)=0\end{cases}\)
结合前面已知值，得到
\(\begin{cases}
E(1,v)=E(1,v-2)\\
S(1,v)=\frac{1+(-1)^v}2+S(1,v-2) \\
T(1,v)=T(1,v-2)\\
TS(1,v) =\frac{1+(-1)^{v-1}}2+TS(1,v-2)\\
F(1,v)=S(1,v)-\frac{1+(-1)^v}2
\end{cases}
\)
然后利用边界条件可以解得
\(\begin{cases}
E(1,v)=0\\
S(1,2k-1)=0; S(1,2k)=k+1 \\
T(1,v)=0\\
TS(1,2k-1)=k;TS(1,2k) =0\\
F(1,2k-1)=0; F(1,2k)=k
\end{cases}
\)
合并后可以得到
\(\begin{cases}
E(1,v)=0\\
S(1,v)=\frac{(v+2)(1+(-1)^v)}4\\
T(1,v)=0\\
TS(1,v)=\frac{(v+1)(1-(-1)^v)}4\\
F(1,v)=\frac{v(1+(-1)^v)}4
\end{cases}
\)
从上面结果可以看出，对于对v的奇偶性进行区分，会容易很多。所以我们可以将上面递推式写成
\(\begin{cases}
E(u,2k)-E(u,2k-2)=S(u-1,2k)+TS(u-1,2k-1)\\
E(u,2k-1)-E(u,2k-3)=S(u-1,2k-1)+TS(u-1,2k-2)\\
S(u,2k)-S(u,2k-2)=E(u-1,2k)+F(u-1,2k-1) \\
S(u,2k-1)-S(u,2k-3)=E(u-1,2k-1)+F(u-1,2k-2) \\
T(u,2k)-T(u,2k-2)=TS(u-1,2k)+S(u-1,2k-1)\\
T(u,2k-1)-T(u,2k-3)=TS(u-1,2k-1)+S(u-1,2k-2)\\
TS(u,2k)-TS(u,2k-2)=F(u-1,2k)+E(u-1,2k-1)\\
TS(u,2k-1)-TS(u,2k-3)=F(u-1,2k-1)+E(u-1,2k-2)\\
F(u,2k)=S(u,2k-2)+TS(u-1,2k)+F(u-1,2k-1)\\
F(u,2k-1)=S(u,2k-3)+TS(u-1,2k-1)+F(u-1,2k-2)
\end{cases}
\)
其中初始值为
\(\begin{cases}
E(0,2k)=1\\E(0,2k-1)=0\\S(0,2k)=0\\S(0,2k-1)=0\\
T(0,2k)=0\\T(0,2k-1)=1\\ST(0,2k)=0\\ST(0,2k-1)=0\\
F(0,2k)=0\\F(0,2k-1)=0
\end{cases}\)
于是可以看出区分v奇偶项以后,所以10个初始值都是k的零次多项式。
由此容易归纳得出，区分v奇偶项以后，所以10个多项式都将是k的u次多项式。
所以我们只需要对u递推计算这10个多项式。最后再将v的值代入对应多项式得出最终结果即可。
不过这个方法为了计算这些多项式如E(u,.),我们还是需要\(O(u^2)\)次计算，时间复杂度还是太高 可以有稍微简化的递推式
E(u,v)-E(u,v-2)=E(u-2,v)+2ST(u-1,v-1)
ST(u,v)-ST(u,v-2)=ST(u-2,v)+E(u-1,v-1)+ST(u-1,v-1)
而且我们仅仅需要计算u+v是偶数的场景，其中初始条件
E(-1,2k-1)=0
E(0,2k)=1 (k>=0)
ST(-1,2k-1)=0
ST(0,2k)=0
比如使用递推可以计算出
E(1,2k-1)=0, ST(1,2k-1)=k (k>=0)
E(2,2k)=(k+1)^2, ST(2,2k)=k(k+1)/2
也可以改为仅包含E的递推式
\(E(u,v)-E(u,v-2)=E(u-2,v)+C_{u+v-2}^{u-1}-E(u-1,v-1)\) 现在设函数\(E_u(x)=\sum_{v=0}^{\infty} E(u,v)x^v\), 于是上面的递推式表示
\((1-x^2)E_u(x)=E_{u-2}(x)+\frac{x}{(1-x)^u}-x E_{u-1}(x)\)
其中\(E_{-1}(x)=0, E_0(x)=\frac1{1-x^2}\)
通过这个方法可以计算出
\(E_1(x)=\frac{x^2}{x^4 - 2x^2 + 1}=x^2 + 2*x^4 + 3*x^6 + 4*x^8+...\)
可以看出奇数项系数都是0，符合E(1,2k-1)=0的结论。唯一不好的地方是偶系数项系数非0，这是因为我们使用递推式式没有考虑只使用一半系数。不过这个不影响对结论的计算。
比如
\(E_2(x)=\frac{-x^2 - x - 1}{x^6 - 3*x^4 + 3*x^2 - 1}=1 + x + 4*x^2 + 3*x^3 + 9*x^4 + 6*x^5 + 16*x^6 + 10*x^7 + 25*x^8+...\)
可以看出\(E(2,2k)=(k+1)^2\)也匹配了，只是多出了没用的奇数项系数。 为了避免另外一半系数出现大片非0值，可以改用递推式
\((1-x^2)E_u(x)=E_{u-2}(x)+\frac12 (\frac{x}{(1-x)^u}+(-1)^{u-1}\frac{x}{(1+x)^u})-xE_{u-1}(x)\)
于是计算结果是
\(E_1(x)=0, E_2(x)=\frac{1+x^2}{1-3x^2+3x^4-x^6}=1+4x^2+9x^4+16x^6+...\)
于是我们可以设\(F_u(x)=(1-x^2)^{u+1}E_u(x)\)
得到
\(F_u(x)=(1-x^2)F_{u-2}(x) -xF_{u-1}(x)+\frac{(x(1+x)^u +(-1)^{u-1} x(1-x)^u)}2\)
是整系数多项式。
比如可以计算出前10个函数为
1 0
2 x^2 + 1
3 2*x^3
4 x^4 + 4*x^2 + 1
5 2*x^5 + 8*x^3
6 3*x^6 + 9*x^4 + 9*x^2 + 1
7 2*x^7 + 20*x^5 + 20*x^3
8 3*x^8 + 30*x^6 + 36*x^4 + 16*x^2 + 1
9 4*x^9 + 36*x^7 + 90*x^5 + 40*x^3
10 3*x^10 + 57*x^8 + 156*x^6 + 100*x^4 + 25*x^2 + 1