mathe 发表于 2014-3-30 15:55:22

A200000和A200749

oeis中这两个序列是计算n*n棋盘上不自相交遍历回路的数目。其中A200749是不考虑对称性的数目,而如果将对称的回路看成同一个,那么数目就是A200000。
这个题目Fans应该
我们可以看到A200749已经被计算到15项了,但是A200000才计算到第10项。但是两者复杂度应该是一样的。

mathe 发表于 2014-3-30 16:01:35

根据burnside引理,计算一个集合在某个群变换下轨道(轨道上就是相互对称)数目即关于群中每个元的不变量的均值

mathe 发表于 2014-3-30 18:41:46

计算A200749可以动态规划,这个fans很清楚。而另外7种(实际只要算4种)对称情况其实可以完全一样的算法,只是每次至少确定两个格子

mathe 发表于 2014-3-31 12:45:35

修正一下,这两序列原来格子可以重复进入,但是边不可重复进入,而且不能自相交。而我提到的是

mathe 发表于 2014-3-31 12:45:42

http://oeis.org/A003763

mathe 发表于 2014-4-1 16:28:11

试着写了个基于STL的代码,在我32位linux算a003763只能到2n=18,而oeis上已经算到2n=22了。主要是内存空间不够了。但是a200749可以轻松算到n=17,oeis还只提供到n=15.当然对于a200000,还需要更复杂的代码处理边缘条件
A200749在n=16和17时取值为
1069049587048126292657245511018395164729584995637677006604201633和
2399885835948485973061191866831331382214612321025714609065977840609754872

mathe 发表于 2014-4-1 18:25:02

上载A3763的代码,而A200749的代码完全类似,只要添加几行代码即可

mathe 发表于 2014-4-2 17:40:44

a200000的程序写好了,好像原序列在n是偶数的时候计算错误了,特别n=6时多了一个,他还给出了图,不知道是否那个图错误或重复了。因为我的程序里面添加了最后模8的计算,如果算出了,最后结果模8还是0的可能性很小
5:A200000:42,A200749:320
6:A200000:9049,A200749:71648
7:A200000:6965359,A200749:55717584
8:A200000:26721852407,A200749:213773992667
9:A200000:429651752290375,A200749:3437213982024260
10:A200000:31194475941824878416,A200749:249555807519163873078
11:A200000:9828395457980805457337560,A200749:78627163663841340597702692
12:A200000:13684686862375136981850895853421,A200749:109477494899001088619906813170744
13:A200000:83297108604256429529069019958551956425,A200749:666376868834051436218404625691790011056
14:A200000:2226741508593975401942934273354241183094830338,A200749:17813932068751803215543399261217225231408150272
15:A200000:260577257822688861848154672171293101310412373160498171,A200749:2084618062581510894785237376608868017658716989948775752

mathe 发表于 2014-4-3 14:50:41

找到程序问题了,get_rotatecount中i=n-1-i需要无条件执行。现在程序可以处理A003763,A200000,A200749,A209077.只是我32位机器只能到边长为17,离22有不小差距,不知道如果64位机器是否会好些
页: [1]
查看完整版本: A200000和A200749