A200000和A200749

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

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

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

×

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位机器是否会好些

账号		自动登录	找回密码
密码			欢迎注册

[擂台] A200000和A200749

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