分割纸片 ProjectEuler#933

iseemu2009

分割纸片

aimisiyou

题目看不懂，是从上一次裁剪下的四个中任选一个么？

iseemu2009

aimisiyou 发表于 2025-5-7 11:43
题目看不懂，是从上一次裁剪下的四个中任选一个么？

每剪一次，从剩余的所有纸片中任选一张。

mathe

这个nim游戏，1*n无法分割，所以是状态0，2*m分割后全是状态0，对应状态1，然后递推计算即可，就是状态数目有点多。

mathe

这个题目我们需要计算wxh矩阵的NIM状态S(w,h),当然S(a,b)=S(b,a)
而S(1,n)=0, S(2,n)=1 (n>=2)
然后计算S(i,j)时，我们需要穷举u,v (1<=u<=i/2, 1<=v<=j/2) ,计算集合
   R(i,j)={S(u,v)^S(i-u,v)^S(u,j-v)^S(i-u,j-v)}
然后不出现在集合里面的最小非负整数就是S(i,j).
比如R(3,3)={S(1,1)^S(1,2)^S(1,2)^S(2,2)}={S(2,2)}={1}, 所以S(3,3)=0
  R(3,4)={S(1,1)^S(1,3)^S(2,1)^S(2,3),S(1,2)^S(1,2)^S(2,2)^S(2,2)}={1,0}, 所以S(3,4)=2
  由于S(2,m)在m>=2都相同，容易得出对于所有S(3,n)=2 (n>=5).

需要注意的是，这是一个通用性质，也就是对于给定的u,每个R(u,v)只有前面若干个需要计算，到了后面某一个后会都相同，而如果前面的若干个R(.,v)中，最多到m需要记录，那么R(u,v)我们最多只需要计算到2m+1项，然后计算完毕后，还可以将最后面完全相同的若干项删除来压缩存储。
通过这种方法，可以轻松计算到R(123,...), 实际计算最大长度在R(123,...)达到3321. 所以这样的空间复杂度不算太大。

此后计算P(w,h)，我们需要统计在计算R(i,j)={S(u,v)^S(i-u,v)^S(u,j-v)^S(i-u,j-v)}时，有多少次达到0，
当然统计过程把对称的情况也要加上，也就是上面如果u和i-u, v和i-v都不同时，实际上需要算4次；而两组有一个不同一个相同，算两次；两组都相同只算1次。
不过现在我计算出来Q(12,123)和题目给出的对不上，还不知道问题出在哪里。

另外需要注意的是题目中给出的H很大，如果我们对每个h都逐项计算累加，会非常消耗时间。实际上由于R(u,.)长度有限，所以对于稍微长一点的数据，会有大量方案得出相同状态，如果它们能够达到0，我们可以统一一次数计数而不需要逐一枚举。

mathe

W在12以内的状态S列表:
s[1]= 1->0
s[2]= 2->1
s[3]= 3->0 4->2
s[4]= 4->1 5->3 6->1
s[5]= 5->0 6->1 7->0 8->4
s[6]= 6->1 7->4 8->3 9->5 10->1 11->7 12->1 13->8 14->1
s[7]= 7->2 8->5 9->4 10->4 11->7 12->4 13->8 14->9 15->8
s[8]= 8->1 9->4 10->1 11->2 12->1 13->8 14->3 15->1 16->2 17->2 18->11 19->1 20->11 21->1 22->1 23->1 24->1 25->1 26->1 27->11 28->1 29->11
s[9]= 9->2 10->3 11->2 12->8 13->0 14->11 15->2 16->11 17->8 18->11 19->8 20->11 21->14 22->11 23->11 24->11 25->11 26->11 27->16 28->14 29->11 30->14 31->14 32->14 33->
14 34->16 35->14 36->16
s[10]= 10->1 11->8 12->8 13->2 14->3 15->8 16->3 17->8 18->9 19->13 20->7 21->14 22->7 23->14 24->1 25->7 26->1 27->7 28->1 29->7
s[11]= 11->0 12->7 13->10 14->4 15->11 16->4 17->11 18->3 19->8 20->15 21->8 22->16 23->8 24->16 25->16 26->16 27->8 28->16 29->8 30->16 31->8 32->16 33->16 34->16 35->1
6 36->16 37->16 38->16 39->16 40->19 41->16 42->16 43->16 44->16 45->16 46->16 47->22 48->16 49->22
s[12]= 12->4 13->4 14->8 15->6 16->10 17->8 18->8 19->16 20->16 21->16 22->5 23->4 24->1 25->7 26->5 27->5 28->16 29->8 30->11 31->8 32->16 33->17 34->19 35->7 36->7 37-
>7 38->7 39->19 40->7 41->2 42->7 43->2 44->7 45->2

mathe

计算部分还是挺快的：
Q(123,1234567)= 5707485980743099