hdu 5015 233 Matrix (构造矩阵,快速幂)

hdu5015题目链接

题意:

给出矩阵的构造规则: a[0][j] (j>=1) 分别为233,2333,23333….给出a[i][0] (i>=1),对于其余的i,j,a[i][j]=a[i-1][j] + a[i][j-1]

现在问a[n][m] 在% 1E7+7 下的值是多少  (n<=10,m<=1E9)

思路:

显然矩阵快速幂,但是不会构造矩阵,放弃。

看了很多题解…发现都是“显然”构造出矩阵。。。似乎是直接凑出来的。。。

可能需要积累一点经验。

对于这道题,我们观察到n很小

所以一个直觉就是从n-1列推到第n列,推到n+1列这样地推。

初始第一列的信息是(假设n为3)

[a1]

[a2]

[a3]

然后我们想要得到

[a1+233]

[a1+a2+233]

[a1+a2+a3+233]

我们发现我们需要233这个常数项体现在矩阵中

而且之后还需要233,2333,23333体现在矩阵中。

那么,我们可以在初始添加23和3两项,这样23…3就都可以构造出来了(我觉得关键点就在这一步,应该是凭借经验吧,虽然刚开始有点难想到orz)

因此现在初始列变成了(其实放置顺序无所谓,不过这样放可以让ai和行数对应,比较友好。

[23]

[a1]

[a2]

[a3]

[3]

设该矩阵为A

现在我们想得到下一列

[233]

[a1+233]

[a1+a2+233]

[a1+a2+a3+233]

[3]

设该矩阵为B

那么现在的问题就是构造一个矩阵5*5的矩阵X,使得X×A=B

凭借直觉(经验?

我们得到这样的矩阵X为

[10,0,0,0,1]

[10,1,0,0,1]

[10,1,1,0,1]

[10,1,1,1,1]

[0,  0,0,0,1]

 

接下来就是矩阵快速幂了,答案是 (X^m)×A.mat[n][0]

 

 

 

 

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz