找回密码
 欢迎注册
查看: 417|回复: 36

[讨论] 阿弥陀签-ProjectEuler 837

[复制链接]
发表于 2025-5-14 09:19:57 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
重排物品问题
重排物品.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-5-14 21:01:27 | 显示全部楼层
其实一条横杠就是代表一次交换操作,我们可以一次交换前两个数(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开头的空格也类似。
通过这种方法,就应该可以极大降低计算量。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-5-17 10:14:12 | 显示全部楼层
这个题目计算的空间复杂度还是有些大。
对于上面的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\)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-5-17 12:19:51 | 显示全部楼层
利用上面方案可以计算出如下10以内的表格,其中E[i,j]代表题目中f(i,j),看上去应该没有问题。
但是使用这种方法计算出来f(321,123)%1234567891应该是847981364,和题目中给定数据不匹配
  1. E[1,0]=0
  2. S[1,0]=1
  3. T[1,0]=0
  4. ST[1,0]=TS[1,0]=0
  5. F[1,0]=0
  6. E[1,1]=0
  7. S[1,1]=0
  8. T[1,1]=0
  9. ST[1,1]=TS[1,1]=1
  10. F[1,1]=0
  11. E[2,0]=1
  12. S[2,0]=0
  13. T[2,0]=0
  14. ST[2,0]=TS[2,0]=0
  15. F[2,0]=0
  16. E[2,1]=0
  17. S[2,1]=0
  18. T[2,1]=2
  19. ST[2,1]=TS[2,1]=0
  20. F[2,1]=1
  21. E[2,2]=4
  22. S[2,2]=0
  23. T[2,2]=0
  24. ST[2,2]=TS[2,2]=1
  25. F[2,2]=0
  26. E[3,0]=0
  27. S[3,0]=1
  28. T[3,0]=0
  29. ST[3,0]=TS[3,0]=0
  30. F[3,0]=0
  31. E[3,1]=0
  32. S[3,1]=0
  33. T[3,1]=0
  34. ST[3,1]=TS[3,1]=2
  35. F[3,1]=0
  36. E[3,2]=0
  37. S[3,2]=4
  38. T[3,2]=1
  39. ST[3,2]=TS[3,2]=0
  40. F[3,2]=3
  41. E[3,3]=2
  42. S[3,3]=0
  43. T[3,3]=0
  44. ST[3,3]=TS[3,3]=7
  45. F[3,3]=0
  46. E[4,0]=1
  47. S[4,0]=0
  48. T[4,0]=0
  49. ST[4,0]=TS[4,0]=0
  50. F[4,0]=0
  51. E[4,1]=0
  52. S[4,1]=0
  53. T[4,1]=3
  54. ST[4,1]=TS[4,1]=0
  55. F[4,1]=2
  56. E[4,2]=7
  57. S[4,2]=0
  58. T[4,2]=0
  59. ST[4,2]=TS[4,2]=3
  60. F[4,2]=0
  61. E[4,3]=0
  62. S[4,3]=2
  63. T[4,3]=14
  64. ST[4,3]=TS[4,3]=0
  65. F[4,3]=10
  66. E[4,4]=28
  67. S[4,4]=0
  68. T[4,4]=0
  69. ST[4,4]=TS[4,4]=12
  70. F[4,4]=0
  71. E[5,0]=0
  72. S[5,0]=1
  73. T[5,0]=0
  74. ST[5,0]=TS[5,0]=0
  75. F[5,0]=0
  76. E[5,1]=0
  77. S[5,1]=0
  78. T[5,1]=0
  79. ST[5,1]=TS[5,1]=3
  80. F[5,1]=0
  81. E[5,2]=0
  82. S[5,2]=7
  83. T[5,2]=3
  84. ST[5,2]=TS[5,2]=0
  85. F[5,2]=6
  86. E[5,3]=5
  87. S[5,3]=0
  88. T[5,3]=0
  89. ST[5,3]=TS[5,3]=20
  90. F[5,3]=0
  91. E[5,4]=0
  92. S[5,4]=28
  93. T[5,4]=17
  94. ST[5,4]=TS[5,4]=0
  95. F[5,4]=32
  96. E[5,5]=34
  97. S[5,5]=0
  98. T[5,5]=0
  99. ST[5,5]=TS[5,5]=60
  100. F[5,5]=0
  101. E[6,0]=1
  102. S[6,0]=0
  103. T[6,0]=0
  104. ST[6,0]=TS[6,0]=0
  105. F[6,0]=0
  106. E[6,1]=0
  107. S[6,1]=0
  108. T[6,1]=4
  109. ST[6,1]=TS[6,1]=0
  110. F[6,1]=3
  111. E[6,2]=11
  112. S[6,2]=0
  113. T[6,2]=0
  114. ST[6,2]=TS[6,2]=6
  115. F[6,2]=0
  116. E[6,3]=0
  117. S[6,3]=5
  118. T[6,3]=31
  119. ST[6,3]=TS[6,3]=0
  120. F[6,3]=26
  121. E[6,4]=59
  122. S[6,4]=0
  123. T[6,4]=0
  124. ST[6,4]=TS[6,4]=43
  125. F[6,4]=0
  126. E[6,5]=0
  127. S[6,5]=34
  128. T[6,5]=119
  129. ST[6,5]=TS[6,5]=0
  130. F[6,5]=103
  131. E[6,6]=238
  132. S[6,6]=0
  133. T[6,6]=0
  134. ST[6,6]=TS[6,6]=137
  135. F[6,6]=0
  136. E[7,0]=0
  137. S[7,0]=1
  138. T[7,0]=0
  139. ST[7,0]=TS[7,0]=0
  140. F[7,0]=0
  141. E[7,1]=0
  142. S[7,1]=0
  143. T[7,1]=0
  144. ST[7,1]=TS[7,1]=4
  145. F[7,1]=0
  146. E[7,2]=0
  147. S[7,2]=11
  148. T[7,2]=6
  149. ST[7,2]=TS[7,2]=0
  150. F[7,2]=10
  151. E[7,3]=11
  152. S[7,3]=0
  153. T[7,3]=0
  154. ST[7,3]=TS[7,3]=41
  155. F[7,3]=0
  156. E[7,4]=0
  157. S[7,4]=59
  158. T[7,4]=54
  159. ST[7,4]=TS[7,4]=0
  160. F[7,4]=84
  161. E[7,5]=88
  162. S[7,5]=0
  163. T[7,5]=0
  164. ST[7,5]=TS[7,5]=203
  165. F[7,5]=0
  166. E[7,6]=0
  167. S[7,6]=238
  168. T[7,6]=225
  169. ST[7,6]=TS[7,6]=0
  170. F[7,6]=340
  171. E[7,7]=450
  172. S[7,7]=0
  173. T[7,7]=0
  174. ST[7,7]=TS[7,7]=578
  175. F[7,7]=0
  176. E[8,0]=1
  177. S[8,0]=0
  178. T[8,0]=0
  179. ST[8,0]=TS[8,0]=0
  180. F[8,0]=0
  181. E[8,1]=0
  182. S[8,1]=0
  183. T[8,1]=5
  184. ST[8,1]=TS[8,1]=0
  185. F[8,1]=4
  186. E[8,2]=16
  187. S[8,2]=0
  188. T[8,2]=0
  189. ST[8,2]=TS[8,2]=10
  190. F[8,2]=0
  191. E[8,3]=0
  192. S[8,3]=11
  193. T[8,3]=57
  194. ST[8,3]=TS[8,3]=0
  195. F[8,3]=51
  196. E[8,4]=116
  197. S[8,4]=0
  198. T[8,4]=0
  199. ST[8,4]=TS[8,4]=105
  200. F[8,4]=0
  201. E[8,5]=0
  202. S[8,5]=88
  203. T[8,5]=319
  204. ST[8,5]=TS[8,5]=0
  205. F[8,5]=308
  206. E[8,6]=557
  207. S[8,6]=0
  208. T[8,6]=0
  209. ST[8,6]=TS[8,6]=533
  210. F[8,6]=0
  211. E[8,7]=0
  212. S[8,7]=450
  213. T[8,7]=1135
  214. ST[8,7]=TS[8,7]=0
  215. F[8,7]=1111
  216. E[8,8]=2270
  217. S[8,8]=0
  218. T[8,8]=0
  219. ST[8,8]=TS[8,8]=1561
  220. F[8,8]=0
  221. E[9,0]=0
  222. S[9,0]=1
  223. T[9,0]=0
  224. ST[9,0]=TS[9,0]=0
  225. F[9,0]=0
  226. E[9,1]=0
  227. S[9,1]=0
  228. T[9,1]=0
  229. ST[9,1]=TS[9,1]=5
  230. F[9,1]=0
  231. E[9,2]=0
  232. S[9,2]=16
  233. T[9,2]=10
  234. ST[9,2]=TS[9,2]=0
  235. F[9,2]=15
  236. E[9,3]=21
  237. S[9,3]=0
  238. T[9,3]=0
  239. ST[9,3]=TS[9,3]=72
  240. F[9,3]=0
  241. E[9,4]=0
  242. S[9,4]=116
  243. T[9,4]=126
  244. ST[9,4]=TS[9,4]=0
  245. F[9,4]=177
  246. E[9,5]=214
  247. S[9,5]=0
  248. T[9,5]=0
  249. ST[9,5]=TS[9,5]=496
  250. F[9,5]=0
  251. E[9,6]=0
  252. S[9,6]=557
  253. T[9,6]=747
  254. ST[9,6]=TS[9,6]=0
  255. F[9,6]=1029
  256. E[9,7]=1197
  257. S[9,7]=0
  258. T[9,7]=0
  259. ST[9,7]=TS[9,7]=2164
  260. F[9,7]=0
  261. E[9,8]=0
  262. S[9,8]=2270
  263. T[9,8]=2758
  264. ST[9,8]=TS[9,8]=0
  265. F[9,8]=3725
  266. E[9,9]=5516
  267. S[9,9]=0
  268. T[9,9]=0
  269. ST[9,9]=TS[9,9]=5995
  270. F[9,9]=0
  271. E[10,0]=1
  272. S[10,0]=0
  273. T[10,0]=0
  274. ST[10,0]=TS[10,0]=0
  275. F[10,0]=0
  276. E[10,1]=0
  277. S[10,1]=0
  278. T[10,1]=6
  279. ST[10,1]=TS[10,1]=0
  280. F[10,1]=5
  281. E[10,2]=22
  282. S[10,2]=0
  283. T[10,2]=0
  284. ST[10,2]=TS[10,2]=15
  285. F[10,2]=0
  286. E[10,3]=0
  287. S[10,3]=21
  288. T[10,3]=94
  289. ST[10,3]=TS[10,3]=0
  290. F[10,3]=87
  291. E[10,4]=210
  292. S[10,4]=0
  293. T[10,4]=0
  294. ST[10,4]=TS[10,4]=213
  295. F[10,4]=0
  296. E[10,5]=0
  297. S[10,5]=214
  298. T[10,5]=706
  299. ST[10,5]=TS[10,5]=0
  300. F[10,5]=709
  301. E[10,6]=1263
  302. S[10,6]=0
  303. T[10,6]=0
  304. ST[10,6]=TS[10,6]=1456
  305. F[10,6]=0
  306. E[10,7]=0
  307. S[10,7]=1197
  308. T[10,7]=3427
  309. ST[10,7]=TS[10,7]=0
  310. F[10,7]=3620
  311. E[10,8]=5697
  312. S[10,8]=0
  313. T[10,8]=0
  314. ST[10,8]=TS[10,8]=6378
  315. F[10,8]=0
  316. E[10,9]=0
  317. S[10,9]=5516
  318. T[10,9]=11692
  319. ST[10,9]=TS[10,9]=0
  320. F[10,9]=12373
  321. E[10,10]=23384
  322. S[10,10]=0
  323. T[10,10]=0
  324. ST[10,10]=TS[10,10]=17889
  325. F[10,10]=0
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-5-17 17:24:16 | 显示全部楼层
调出bug了,公式抄错了一个地方。
现在主要问题是复杂度太高,
比如f(123,321)可以0.002s得出172633303
f(12345,54321)需要4.618s得出232961944.

点评

如果要保密,可否加QQ私发一下。  发表于 2025-5-17 17:56
可否分享一下通俗的思考过程?或者把源代码发布一下,学习学习。  发表于 2025-5-17 17:52
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-5-17 18:04:55 | 显示全部楼层
现在验证了公式
\(\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}
\)


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-5-17 20:40:36 | 显示全部楼层
从上面结果可以看出,对于对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)\)次计算,时间复杂度还是太高
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-5-18 15:26:32 | 显示全部楼层
可以有稍微简化的递推式
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)\)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-5-18 16:39:54 | 显示全部楼层
现在设函数\(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\)也匹配了,只是多出了没用的奇数项系数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-5-18 17:12:41 | 显示全部楼层
为了避免另外一半系数出现大片非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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2025-6-4 21:34 , Processed in 0.049990 second(s), 21 queries .

Powered by Discuz! X3.5

© 2001-2025 Discuz! Team.

快速回复 返回顶部 返回列表