马踏棋盘回路计数问题

mathe

将数据用hash散列到文件可能不如选择固定几个连续位置的值作为文件名更加好 由于每次添加一个格子仅改变少量位置取值，这样可以保证每个文件数据仅产生出少量文件的数据，可以改善数据缓存的效率（另外每个文件数据 ... mathe 发表于 2011-6-2 22:08

采用固定位置作为文件编号还有一个好处。由于我们知道每次添加格子仅仅改变少量位置取值，所以对于每个文件，经过变换后产生的数据只会写入少量几个文件。同样，我们可以将输入文件分组，使得每组内部的文件经过变换后产生的数据都只会写入少量几个文件。而这时，如果文件数目足够大，那么这几个少量文件数据总量不会太大，所以这时，排序合并之前的数据我们更本没有必要写入文件，直接放在内存即可，等到数据排序合并处理以后一下子写入文件中即可。而由于排序合并之前的文件是最大的，这样应该可以大量减少对磁盘的访问

mathe

8*9和8*10都出来了 7112881119092574 4235482818156697040 不过9*2n就不敢运行了，怕磁盘空间不够，把机器运行死了

KeyTo9_Fans

看来台式机的运行速度比笔记本电脑快不少。 不能直接运行9*10棋盘，因为数组和文件数量都不够大。 9*10棋盘需要重新写一个程序。 分500个文件写是不够的。 估计要写10000个文件以上。 列一下8*6到8*10的答案。（目前仅缺8*8棋盘的答案没有公布） 还有中间状态数的峰值。 我根据这些数据再估计一下运行9*10棋盘所消耗的资源。

mathe

8*8的数据oeis上有的，所以我就没有抄写下来。 13267364410532 至于文件数目，我试着在我机器上修改到2000个以上程序就出问题了（可能是同时打开文件数目达到上限了）。

mathe

Fans还可以计算一下7*(2n)每个结果模2^64-1的结果（也就是每次相加时判断，如果结果会大于2^64-1,把和再加1即可）。然后我们使用中国剩余定理就可以求出对应的结果了。 我现在重新计算8*n,并且分别计算模2^64和模2^64-1的结果。

xbtianlang

a=x mod (2^64-1) b=x mod (2^64) y=(2^128-2^64+a*2^64-b*(2^64-1)) mod (2^128-2^64) x=y 当x<2^128-2^64 时。

mathe

由于机器出现问题,没有在预期时间全部达到结果,现在已经有部分8*n的结果，可以先贴出

n	$mod(2^64)$	$mod(2^64-1)$	$mod(2^64-3)$	result
5	44202	44202	44202	44202
6	55488142	55488142	55488142	55488142
7	34524432316	34524432316	34524432316	34524432316
8	13267364410532	13267364410532	13267364410532	13267364410532
9	7112881119092574	7112881119092574	7112881119092574	7112881119092574
10	4235482818156697040	4235482818156697040	4235482818156697040	4235482818156697040
11	1504665377347155052	1504665377347155165	1504665377347155391	2085986745706526487660
12	17980416878068033778	17980416878068093701	17980416878068213547	1105402225545775529519346
13	752244656655620712	752244656687432289	752244656751055443	586820020252349733523479144
14	7602272457316264568	7602272474205470847	7602272507983883405	311550865844403670432538061432
15	13841467888904518702	13841476709057854188	13841494349364525160	162703111270599746594928785964078
16	8176313932395293354		8190270518723441621	85817858712661606753131465774443178
17	1098358518885749032		8448288329966564092	45194091394912063170099393989692461352
18	18375149731352769846		16105077287275103238	326323885119378112085100727490253780278
19	1269613588780643810		14025668667217352234
20	5123704852959061782		4504750716462361971

mathe

昨天试着运行了一下6*2n问题的模$2^64-1$结果的前30项，结果得到后面若干项结果同网上公布结果不匹配，有点奇怪，不知道是我的代码有问题还是什么（比如网上数据有误？），代码中我仅修改了: if(k

xbtianlang

我以为直接模加，可能先模$2^64$了，先判断$2^64-1-vi$与$v[c[k]]$的大小，再加或减。

mathe

Fans有空查看一下，估计是我代码改的有问题，6×n的结果模$2^64$没有问题，同网络上的一致

2. #include<cstdio>
3. #include<memory>
4. #include<algorithm>
5. #include <string.h>
6. using namespace std;
7. #define __int64 long long
8. const unsigned int pm=503,pn=8388608;
9. char fn[96];
10. unsigned char a[20],b[20];
11. unsigned int c[pn],h,i,j,k,l,m,n,t;
12. unsigned long long o;
13. unsigned __int64 ui,vi,ans[32],u[pn],v[pn];
14. FILE *ou[pm],*in;
15. #ifndef MODR
16. #define MODR 0
17. #endif
19. unsigned __int64 add(unsigned __int64 x, unsigned __int64 y)
20. {
21. if(MODR==0)return x+y;
22. if((-MODR)-x>y)return x+y;
23. return x+y+MODR;
24. }
26. void pr(unsigned int f,unsigned __int64 v)
27. {
28. fwrite(&v,sizeof(unsigned __int64),1,ou[f]);
29. }
31. void pri(unsigned __int64 v)
32. {
33. fwrite(&v,sizeof(unsigned __int64),1,in);
34. }
36. void sc(unsigned int f,unsigned __int64 &v)
37. {
38. if(fread(&v,sizeof(unsigned __int64),1,ou[f])!=1)v=0ull;
39. }
41. void sci(unsigned __int64 &v)
42. {
43. if(fread(&v,sizeof(unsigned __int64),1,in)!=1)v=0ull;
44. }
46. unsigned __int64 id(unsigned char a[])
47. {
48. unsigned char c[16],i,j;
49. unsigned __int64 s;
50. memset(c,0,16);
51. for(i=0;i<l;i++)
52. {
53. j=a[i];
54. if(j>1)
55. if(c[j])
56. {
57. a[c[j]-1]=i-c[j]+2;
58. a[i]=0;
59. }
60. else c[j]=i+1;
61. }
62. s=0;
63. for(i=0;i<l;i++)
64. s=s*(l+1-i)+a[i];
65. return s;
66. }
68. void ar(unsigned __int64 x)
69. {
70. unsigned char i,j,k;
71. k=2;
72. for(i=l+1;i;)
73. {
74. i--;
75. j=l-i+1;
76. a[i]=char(x%j);
77. x/=j;
78. if(a[i]>1)
79. {
80. a[i+a[i]-1]=k;
81. a[i]=k++;
82. }
83. }
84. }
86. void ad(unsigned __int64 x)
87. {
88. unsigned __int64 s;
89. s=id(b);
90. pr(s%pm,s);
91. pr(s%pm,x);
92. o++;
93. }
95. unsigned int d(unsigned int x)
96. {
97. unsigned int i;
98. for(i=1;;i++)
99. if(i!=x&&a[i]==a[x])return i;
100. }
102. void c1(unsigned int x)
103. {
104. unsigned int i,j;
105. if(a[x]==1)return;
106. memcpy(b,&a[1],l);
107. if(a[x]==a[0])
108. {
109. j=h/m+2;
110. b[x-1]=1;
111. for(i=0;i<l;i++)
112. if(h+i+1<j*m&&b[i]!=1||h+i+2>j*m&&b[i]!=0)break;
113. if(i>=l)ans[j]=add(ans[j],vi);
114. return;
115. }
116. if(!a[x])b[x-1]=a[0];
117. else
118. {
119. b[x-1]=1;
120. b[d(x)-1]=a[0];
121. }
122. ad(vi);
123. }
125. void c2(unsigned int x,unsigned int y)
126. {
127. unsigned int i,j;
128. if(a[x]==1||a[y]==1)return;
129. memcpy(b,&a[1],l);
130. if(a[x]&&a[x]==a[y])
131. {
132. j=h/m+2;
133. b[x-1]=1;
134. b[y-1]=1;
135. for(i=0;i<l;i++)
136. if(h+i+1<j*m&&b[i]!=1||h+i+2>j*m&&b[i]!=0)break;
137. if(i>=l)ans[j]=add(ans[j],vi);
138. return;
139. }
140. if(a[x])
141. {
142. b[x-1]=1;
143. b[y-1]=1;
144. if(a[y])b[d(y)-1]=a[x];
145. else b[y-1]=a[x];
146. }
147. else
148. if(a[y])
149. {
150. b[x-1]=a[y];
151. b[y-1]=1;
152. }
153. else
154. {
155. b[x-1]=15;
156. b[y-1]=15;
157. }
158. ad(vi);
159. }
161. bool cmp(unsigned int i,unsigned int j)
162. {
163. return u[i]<u[j];
164. }
166. int main()
167. {
168. scanf("%d%d",&n,&m);
169. //n=10;
170. //m=8;
171. l=m+m+1;
172. b[m+1]=2;
173. b[m+m]=2;
174. vi=id(b);
175. for(i=0;i<pm;i++)
176. {
177. sprintf(fn,"sa/%04d.dat",i);
178. ou[i]=fopen(fn,"wb");
179. if(vi%pm==i)
180. {
181. pr(i,vi);
182. pr(i,1);
183. }
184. fclose(ou[i]);
185. }
186. for(h=1;h<n*m-m;h++)
187. {
188. o=0;
189. j=h%m;
190. for(i=0;i<pm;i++)
191. {
192. sprintf(fn,"sb/%04d.dat",i);
193. ou[i]=fopen(fn,"wb");
194. }
195. for(i=0;i<pm;i++)
196. {
197. sprintf(fn,"sa/%04d.dat",i);
198. in=fopen(fn,"rb");
199. while(1)
200. {
201. sci(ui);
202. if(!ui)break;
203. sci(vi);
204. ar(ui);
205. if(a[0]==1)
206. {
207. memcpy(b,&a[1],l);
208. ad(vi);
209. continue;
210. }
211. if(a[0]>1)
212. {
213. if(j>1)c1(m-2);
214. if(j&&h/m<n-2)c1(m+m-1);
215. if(j<m-1&&h/m<n-2)c1(m+m+1);
216. if(j<m-2)c1(m+2);
217. continue;
218. }
219. if(j>1)
220. {
221. if(h/m<n-2)c2(m-2,m+m-1);
222. if(j<m-1&&h/m<n-2)c2(m-2,m+m+1);
223. if(j<m-2)c2(m-2,m+2);
224. }
225. if(j&&h/m<n-2)
226. {
227. if(j<m-1)c2(m+m-1,m+m+1);
228. if(j<m-2)c2(m+m-1,m+2);
229. }
230. if(j<m-2&&h/m<n-2)c2(m+m+1,m+2);
231. }
232. fclose(in);
233. in=fopen(fn,"wb");
234. fclose(in);
235. // printf("%c%c%c%d",8,8,8,i);
236. }
237. // printf(" ");
238. for(i=0;i<pm;i++)
239. {
240. fclose(ou[i]);
241. }
242. for(i=0;i<pm;i++)
243. {
244. sprintf(fn,"sb/%04d.dat",i);
245. ou[i]=fopen(fn,"rb");
246. t=0;
247. while(1)
248. {
249. sc(i,ui);
250. if(!ui)break;
251. u[t]=ui;
252. sc(i,v[t]);
253. c[t]=t++;
254. }
255. fclose(ou[i]);
256. sprintf(fn,"sb/%04d.dat",i);
257. ou[i]=fopen(fn,"wb");
258. fclose(ou[i]);
259. sort(c,c+t,cmp);
260. sprintf(fn,"sa/%04d.dat",i);
261. in=fopen(fn,"wb");
262. vi=v[c[0]];
263. for(k=1;k<=t;k++)
264. if(k<t&&u[c[k]]==u[c[k-1]])vi=add(vi,v[c[k]]);
265. else
266. {
267. pri(u[c[k-1]]);
268. pri(vi);
269. if(k<t)vi=v[c[k]];
270. }
271. fclose(in);
272. // printf("%03d%c%c%c",i,8,8,8);
273. }
274. // printf("%c%d %d: %llu\n",13,h/m,j,o);
275. if(j>m-2){printf("%llu\n",ans[h/m+2]);fflush(stdout);}
276. }
277. // scanf("%d",&h);
278. return 0;
279. }

复制代码