[leetcode/lintcode 题解] 算法面试真题：233矩阵 · 233 Matrix

描述
给出一个矩阵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]]

算法：矩阵快速幂
快速幂：

• 这是一种简单而有效的小算法，它可以以O(logn)的时间复杂度计算乘方

• 举个例子，我们计算7^10，我们把10写成二进制的形式，也就是 (1010)2

  • 现在问题转变成了计算7^(1010)2，显然我们可以将7^(1010)2拆分成7^(1000)2，7^(10)2。实际上，对于任意的整数，我们都可以把它拆成若干个7^(1000....)2的形式相乘。而这恰好就是7^1、7^2、7^4……我们只需不断把底数平方就可以算出答案
  • 我们计算a的n次

  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' ;
用数学归纳法可以得出递推式：

• f(n,m)=f(n,m-1)*10+3;
• f(n,m) = f(n-1,m)+f(n,m-1) = f(n,m-1)+f(n-1,m-1)+f(n-2,m-1)+...+f(1,m-1)+f(0,m-1)*10+3;

然后我们建立矩阵：

构造矩阵得到了，我们就可以通过矩阵快速幂快速求答案了
复杂度分析

• 时间复杂度O(logn * L^3)

  • 快速幂的复杂度为logn量级
  • L为矩阵边长，矩阵乘法为n^3量级

• 空间复杂度O(L^2)

  • 矩阵的大小为L*L

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