python-盾神与砝码称重

解题思路:

用python翻译了一下第3个用c++写的题解的大佬的代码，真的很厉害，要多学习一下dfs算法，这道题真的可以用来好好的理解dfs算法的用法。可以当作典例来看。

假设法码放在左边的盘子里，物品放在右边的盘子里，每一颗法码都有三种状态

①放在左边

②不放

③放在右边

对所给的每一颗法码都列举出这三种状态，然后进行深度搜索，对第二颗法码再次列举出这三种状态......，直到左盘的重量和右盘的重量相等，或者不能称出物品重量。

注意事项:

法码既可以放在左边，也可以放在右边，也可以不放。

参考代码:

def mul(flag):  
    global m  
    global A  
    global AA  
  
    temp = [[0,0],[0,0]]  
    if flag == 1:  
        B = A[:]  
    elif flag == 2:  
        B = AA[:]  
  
    for i in range(2):  
        for j in range(2):  
            for k in range(2):  
                temp[i][j] = temp[i][j] + A[i][k]*B[k][j]      
    
    for i in range(2):  
        for j in range(2):  
            A[i][j] = temp[i][j] % m  
  
def f(b):  
    global m  
    global A  
  
    if b == 0:  
        A[0] = [1%m,0]  
        A[1] = [0,1%m]  
        return   
  
    if b % 2 == 0:  
        b = b // 2  
        f(b)                          #注意f()和mul()不要写反了。先递归调用的最后一层，然后依次往外乘。  
        mul(1)  
        return  
  
    if b % 2 == 1:  
        b = b - 1  
        f(b)  
        mul(2)  
        return  
  
  
if __name__ == '__main__':  
    b,m = map(int,input().split())  
    A = [[int(i) for i in input().split()]]  
    A = A + [[int(i) for i in input().split()]]  
    AA = A[:]  
  
    f(b)  
    for i in range(2):  
        for j in range(2):  
            print(A[i][j],end=' ')  
        print()