狗万登陆 >狗万登陆 >解决编程中的数学问题! “交叉词”问题的解释 >

解决编程中的数学问题! “交叉词”问题的解释

2019-09-12 02:02:22 来源:环球网
A+ A-

审查问题

在填字游戏板上,在网格方块中放置白色或黑色方块。

以下是将白色和黑色方块放置在3列×4个正方形中的示例。

解决编程中的数学问题! “交叉词”问题的解释

以下规则适用于白色和黑色方块的排列。
白色物质的面积不应除以黑色质量。
黑色方块不得垂直或水平连续。

例如,以下是不正确放置的示例。

解决编程中的数学问题! “交叉词”问题的解释

对于自然数n,将白色和黑色正方形放置在3个垂直×n个水平方格上时的数量定义为F(n)。

例如,F(1)= 4且F(2)= 11。 以下显示如何安排n = 2。

解决编程中的数学问题! “交叉词”问题的解释

类似地,可以确认F(3)= 39,F(4)= 121,F(5)= 387。

标准输入给出自然数n(1 n n 108 108)。
编写一个程序,将剩余的F(n)除以106输出到标准输出。

政策:分为一个案例。 但是有一些陷阱......

在填字游戏中找到有效板数是一个问题。 过去,CodeIQ存在相同的配置问题。 电路板的最大尺寸为5×6,但在这种情况下为3×108,侧面非常长。 关键是要成功使用此功能。

首先,直截了当的解决方案是列出满足条件的所有电路板。 如果电路板很小,这种方法将起作用。 但是,我认为你很容易想象在这么大的尺寸下,事情根本无法发挥作用。

所以,在这个问题中,让我们使用“ 专注于前面的一个状态 ”的概念经常出现在本文中( )。 关于自然数n,我们将考虑当尺寸为n时3×n和3×(n + 1)之间的关系。

首先是配方。 如何在3×n中排列白色方块和黑色方块将根据最右列的排列分为以下5种类型。

解决编程中的数学问题! “交叉词”问题的解释

让每种情况下的数字为An,Bn,Cn,Dn,En。

假设你知道An,...,En的所有值。 在这种情况下,如何在n + 1的情况下获得数,即An + 1,Bn + 1,Cn + 1,Dn + 1,En + 1?

以An + 1为例。 该布置使得最右边的列是图案1。 下一个左列可以具有模式1到5中的任何一个,因此递归公式An + 1 = An + Bn + Cn + Dn + En成立。

解决编程中的数学问题! “交叉词”问题的解释

如果我们对Bn,Cn,Dn,En做同样的事情,我们可以推导出递归公式,但这里有一个很大的缺陷。 例如,Bn + 1,即右端是模式2。 乍一看,模式3可能会来到这个左栏。 但是,如果左相邻列的顶部(左起第n列)是白色,则没有问题,但如果是黑色,则创建分割区域。

解决编程中的数学问题! “交叉词”问题的解释

换句话说,这个问题不足以仅查看左相邻列(第n列),我们还必须考虑左相邻列(第n-1列)。

让我们细分模式3 有四种方式。 根据是黑色还是白色,n-1列的顶部(或底部)被分成三个,并且在每种情况下的数字是C(a)n,C(b)n,C(c)n。 另外,n-1列可以是外壁(需要n = 1)。 在这种情况下的数字是C(d)n。

解决编程中的数学问题! “交叉词”问题的解释

我们将在上述八种模式中得出复发。 例如,对于Bn + 1,如果左相邻列是模式1,3a,4,则可以在n + 1列中找到模式2。 因此,Bn + 1 = An + C(a)n + Dn。

解决编程中的数学问题! “交叉词”问题的解释

其他变量也是如此。 省略详细过程。 结果如下。 以矩阵的形式表达。

解决编程中的数学问题! “交叉词”问题的解释

之后,列向量(A1,B1,C(a)1,C(b)1,C(c)1,C(d)1,D1,E1)=(1,1,0,0)作为初始值上述矩阵重复乘以(n-1)次,分别为0,1,1,1)。 得到的列向量是在最右边的列序列中排序的3×n网格。 由于图案3b,3c和3d是不合适的,因此其他组件的总和是要寻求的答案。

履行

让我们实现上述目标。 由于这次n的上限与108一样大,因此处理时间n次矩阵乘法并不好。 让我们用矩阵功率高速计算。 ( )

代码示例如下。 请注意,从答案中减去一个例外,因为模式5仅在n = 1时不适用。

D = 1000000

def mul(x,y):
z = [[0表示范围内的i(len(y [0]))] j表示范围(len(x))]
对于范围内的i(len(x)):
对于范围内的j(len(y [0])):
对于范围内的k(len(x [0])):
z [i] [j] =(z [i] [j] + x [i] [k] * y [k] [j])%D
返回z

def pow(x,m):
如果m == 1:返回x
如果m%2 == 0:
p = pow(x,m / 2)
返回多个(p,p)
其他:
p = pow(x,m-1)
return mul(x,p)

矩阵= [
[1,1,1,1,1,1,1,1],
[1,0,1,0,0,0,1,0],
[1,0,0,0,0,0,0,0],
[0,1,0,0,0,0,0,0],
[0,0,0,0,0,0,1,0],
[0,0,0,0,0,0,0,0],
[1,1,1,0,0,0,0,0],
[1,0,0,0,0,0,0,0],
]

vector = [[1],[1],[0],[0],[0],[1],[1],[1]]

n = int(input())
p = pow(矩阵,n-1)
q = mul(p,vector)
answer = q [0] [0] + q [1] [0] + q [2] [0] + q [6] [0] + q [7] [0]
如果n == 1:answer- = 1

打印答案%D

除了上面提到的矩阵幂之外,还有一种加速方法,它使用106处余数的周期性( )。 我会省略细节。

每个人的代码

这个问题的挑战者的代码和发布代码的代码在Togetter中汇总在一起。 (我们会随时添加。)请检查一下。

来自CodeIQ管理办公室

谢谢你,Kawazoe先生!
请期待下一期Kawazoe。

责任编辑:郜梦借 CN037