首页 > 试题广场 >

魔力手环

[编程题]魔力手环

热度指数：5031 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小易拥有一个拥有魔力的手环上面有n个数字(构成一个环),当这个魔力手环每次使用魔力的时候就会发生一种奇特的变化：每个数字会变成自己跟后面一个数字的和(最后一个数字的后面一个数字是第一个),一旦某个位置的数字大于等于100就马上对100取模(比如某个位置变为103,就会自动变为3).现在给出这个魔力手环的构成，请你计算出使用k次魔力之后魔力手环的状态。

输入描述:

输入数据包括两行： 第一行为两个整数n(2 ≤ n ≤ 50)和k(1 ≤ k ≤ 2000000000),以空格分隔 第二行为魔力手环初始的n个数，以空格分隔。范围都在0至99.

输出描述:

输出魔力手环使用k次之后的状态，以空格分隔，行末无空格。

示例1

输入

3 2 1 2 3

输出

8 9 7

算法知识视频讲解

Python

牛客558275203号

矩阵快速乘的Python3版本，时间复杂度 $图片说明$ ，通过100%样例。

n, k = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]


m = str(bin(k))[2:]    # k的二进制形式
m = m[::-1]
z = 100
# 矩阵乘法, O(n*k*m)
def matMul(a, b):    
    n, k, m = len(a), len(b), len(b[0])
    c = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            c[i][j] = sum([a[i][l]*b[l][j] for l in range(k)]) % z
    return c



# 关系矩阵, O(n^2)
corM = [[0]*n for _ in range(n)]    
for i in range(n):
    corM[i][i] = corM[i][(i+1)%n] = 1
    

# 求关系矩阵的2, 4, 8, ..., 2^(log2(k))次幂, O(log(k)*n^3)
mats = [corM]    
for i in range(len(m)-1):
    mats.append(matMul(mats[-1], mats[-1]))
    

# 求关系矩阵的k次幂, O(log(k)*n^3)
corM = mats[-1]    
for i in range(len(m)-1):
    if m[i] == '1':
        corM = matMul(corM, mats[i])



# 求原向量经k次变换后的结果, O(n^2)
res = matMul(corM, [[a] for a in x])    
res = [a[0] for a in res]
print(' '.join(map(str, res)))

编辑于 2020-04-07 11:20:55 回复(0)

Python

SrCMpunk

# -*- coding:utf-8 -*- 
import numpy as np 
def creatMat(n):
    mat_1 = np.eye(n, M=None, k=0).astype(int)
    mat_2 = np.eye(n, M=None, k=1).astype(int)
    mat_result = mat_1 + mat_2
    mat_result[n-1][0] = 1  
    return mat_result 
if __name__ == '__main__':
    input_n_k = raw_input().strip()
    input_data = raw_input().strip()

    n = int(input_n_k[0])
    k = int(input_n_k[2:])

    dt = np.matrix(input_data.split())
    dt = dt.astype(int)
    dt.shape = (n,1)
    dt.transpose()

    matmulti = creatMat(n) for i in range(0, k):
    dt = np.dot(matmulti, dt)
    dt = dt%100  dt_out = dt.transpose()
    s_out = str(dt_out[0,:]) 
    print s_out[2:-2]

可怜了我们pytho的用户，速度怎么比得过C++

编辑于 2017-03-27 11:14:10 回复(0)