更新时间:2022-03-05 03:20:58
描述
给出一个矩阵A,矩阵的第一行是0,233,2333,23333...(也就是说,A(0,0)=0,A(0,1)=233,A(0,2)=2333,A(0,3)=23333...),除此之外,A(i,j)=A(i-1,j)+A(i,j-1)。
给出一个拥有n个整数的数组X,X[i]表示A(i+1,0),(也就是说X[0]表示A(1,0),X[1]表示A(2,0)...),以及一个正整数m。
求A(n,m)%10000007的值。
n <=10, m <= 10^9
0 =< A(i,0) < 2^31
在线评测地址:领扣题库官网
样例1
输入: X=[1], m=1
输出: 234
解释:
[[0,233],
[1,234]]
样例2
输入: X=[0,0], m=2
输出: 2799
解释:
[[0,233,2333],
[0,233,2566],
[0,233,2799]]
算法:矩阵快速幂
快速幂:
举个例子,我们计算7^10,我们把10写成二进制的形式,也就是 (1010)2
function:qpow(a,n)
ans=1
while n>0:
if n&1 //如果n的当前末位为1
ans*=a //ans乘上当前的a
a*=a //a自乘
n >>= 1 //n往右移一位
return ans
快速幂的进一步就是矩阵快速幂,两者的区别就是,一个是数字,一个是矩阵
对于这题,首先找到原态和现态的关系,233,2333,23333,23333, 这些数都遵循 a0=a0'10+3 a1=a0'10+3+a1' ; a2=a0'10+3+a1'+a2' ; a3=a0'10+3+a1'+a2'+a3' ;
用数学归纳法可以得出递推式:
然后我们建立矩阵:
构造矩阵得到了,我们就可以通过矩阵快速幂快速求答案了
复杂度分析
时间复杂度O(logn * L^3)
空间复杂度O(L^2)
class Solution:
"""
@param org: a permutation of the integers from 1 to n
@param seqs: a list of sequences
@return: true if it can be reconstructed only one or false
"""
def sequenceReconstruction(self, org, seqs):
graph = self.build_graph(seqs)
topo_order = self.topological_sort(graph)
return topo_order == org
def build_graph(self, seqs):
# initialize graph
graph = {}
for seq in seqs:
for node in seq:
if node not in graph:
graph[node] = set()
for seq in seqs:
for i in range(1, len(seq)):
graph[seq[i - 1]].add(seq[i])
return graph
def get_indegrees(self, graph):
indegrees = {
node: 0
for node in graph
}
for node in graph:
for neighbor in graph[node]:
indegrees[neighbor] += 1
return indegrees
def topological_sort(self, graph):
indegrees = self.get_indegrees(graph)
queue = []
for node in graph:
if indegrees[node] == 0:
queue.append(node)
topo_order = []
while queue:
if len(queue) > 1:
# there must exist more than one topo orders
return None
node = queue.pop()
topo_order.append(node)
for neighbor in graph[node]:
indegrees[neighbor] -= 1
if indegrees[neighbor] == 0:
queue.append(neighbor)
if len(topo_order) == len(graph):
return topo_order
return None
更多题解参考:九章官网solution