首页 > 试题广场 >

魔力手环

[编程题]魔力手环
  • 热度指数：5035 时间限制：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
算法知识视频讲解
添加回答
Java
YiBuLZ头像 YiBuLZ 
import java.util.Scanner;
//请见http://blog.csdn.net/zheng548/article/details/71075163

public class Main {
    /**
     * 利用矩阵快速幂
     参考：http://www.cnblogs.com/vongang/archive/2012/04/01/2429015.html
     http://www.lai18.com/content/1108003.html?from=cancel
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        //用一个二维数组存储
        int[][] arr= new int[1][n];
        for (int i = 0; i < n; i ++) {
            arr[0][i] = sc.nextInt();
        }
        //初始化单元矩阵
        int[][] mul = new int[n][n];
        for (int i = 0; i < n; i ++) {
                if (i < n - 1) {
                    mul[i][i] = 1;
                    mul[i + 1][i] = 1;
                } else {
                    mul[i][i] = 1;
                    mul[0][i] = 1;
                }
        }

        for (; k > 0; k >>= 1) {
           if ((k & 1) == 1) {
               arr = Core(arr, mul);
           }
           mul = Core(mul, mul);
        }
        int i;
        for (i = 0; i < n - 1; i ++) {
            System.out.print(arr[0][i] + " ");
        }
        System.out.println(arr[0][i]);
    }

    private static int[][] Core(int[][] a, int[][] b) {
        int rowRes = a.length;
        int columnRes = b[0].length; //TODO:
        int columnA = a[0].length; // == b.length;

        int[][] c = new int[rowRes][columnRes];
        for (int i =0; i < rowRes; i ++) {
            for (int j = 0; j < columnRes; j ++) {

                for (int k = 0; k < columnA; k ++) {
                    if (a[i][k] == 0 || b[k][j] == 0) {
                        continue;          //剪枝
                    }

                    c[i][j] += a[i][k] * b[k][j];
                }
                //100取余运算
                if (c[i][j] >= 100) {
                    c[i][j] %= 100;
                }
            }
        }
        return c;
    }

}


编辑于 2017-05-01 20:52:32 回复(3)
Java
旭>_头像 旭>_
贴一个java的 
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	// 矩阵乘法加对100取余
	private static int[][] mutAndMod(int[][] a,int[][] b){
		int n1 = a.length;
		int n2 = a[0].length;
		int[][] ret = new int[n1][n2];
		for(int i=0;i<n1;i++){
			for(int j=0;j<n2;j++){
				int temp = 0;
				for(int k=0;k<n2;k++){
					temp += a[i][k] * b[k][j];
				}
				ret[i][j] = temp%100;
			}
		}
		return ret;
		
	}
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n = sc.nextInt();
			int k = sc.nextInt();
			int[][] band = new int[1][n];
			for(int i=0;i<n;i++){
				band[0][i] = sc.nextInt();
			}
			int[][] src = new int[n][n];
			for(int i=0;i<n;i++){
				if(i+1<n){
					src[i][i] = 1;
					src[i+1][i] = 1;
				}else{
					src[i][i] = 1;
					src[0][i] = 1;
				}
			}
            // 结果
			int[][] ans = new int[1][n];
			for(int i=0;i<n;i++){
				ans[0][i] = band[0][i];
			}
            /*
			for(int i=0;i<n;i++){
				System.out.println(Arrays.toString(src[i]));
			}
			*/
			while(k>0){
				if(k%2==1){
					ans = mutAndMod(ans,src);
				}
				//System.out.println(Arrays.toString(ans[0]));
				src =  mutAndMod(src,src);
				k >>=1;
				
			}	
            System.out.print(ans[0][0]);
            for(int i=1;i<n;i++){
                System.out.print(" " + ans[0][i]);
            }
            System.out.println();
			
		}
		sc.close();
	}
	
}

发表于 2017-03-28 17:41:48 回复(3)
C/C++
ouge头像 ouge 
#include <iostream>
#include <vector>

using namespace std;

void matrixMultiply(vector<vector<int>> &a, vector<vector<int>> &b) {
  vector<vector<int>> c(a.size(), vector<int>(b[0].size(), 0));
  for (int i = 0; i < c.size(); i++) {
    for (int j = 0; j < c[0].size(); j++) {
      for (int k = 0; k < b.size(); k++) {
        c[i][j] += a[i][k] * b[k][j];
      }
      c[i][j] %= 100;
    }
  }
  swap(a, c);
}

int main() {
  int n, k;
  cin >> n >> k;
  vector<vector<int>> nums{vector<int>(n, 0)};
  vector<vector<int>> marix(n, vector<int>(n, 0));

  for (auto &a : nums[0]) {
    cin >> a;
  }

  for (int i = 0; i < n - 1; i++) {
    marix[i][i] = 1;
    marix[i + 1][i] = 1;
  }
  marix[n - 1][n - 1] = 1;
  marix[0][n - 1] = 1;

  while (k) {
    if (k & 1) {
      matrixMultiply(nums, marix);
      k--;
    } else {
      k >>= 1;
      matrixMultiply(marix, marix);
    }
  }

  bool printflag = false;
  for (auto &a : nums[0]) {
    if (printflag) {
      cout << ' ' << a;
    } else {
      cout << a;
      printflag = true;
    }
  }

  cout << endl;
}

发表于 2017-05-05 13:38:30 回复(2)
C/C++
BoilTask头像 BoilTask
构造矩阵，然后使用矩阵快速幂即可
时间复杂度O( n^3 * log(k) ) 
#include <cstdio>
typedef long long LL;
struct Mat {
	int N,M;
	int m[52][52];
};

Mat MatMul(Mat A,Mat B,LL MOD) {
	Mat tmp;
	tmp.N=A.N;
	tmp.M=B.M;
	for(int i=0; i<A.N; i++) {
		for(int j=0; j<B.M; j++) {
			int sum=0;
			for(int k=0; k<B.N; k++)
				if(MOD)
					sum=(sum+A.m[i][k]*B.m[k][j])%MOD;
				else
					sum+=A.m[i][k]*B.m[k][j];
			tmp.m[i][j]=sum;
		}
	}
	return tmp;
}
Mat MatPow(Mat mat,LL n,LL MOD) {
	Mat ans;
	ans.N=ans.M=mat.N;
	for(int i=0; i<ans.N; i++)
		for(int j=0; j<ans.M; j++)
			if(i==j)
				ans.m[i][j]=1;
			else
				ans.m[i][j]=0;
	while(n) {
		if(n&1)
			ans=MatMul(ans,mat,MOD);
		mat=MatMul(mat,mat,MOD);
		n>>=1;
	}
	return ans;
}
void MatPr(Mat t) {
	for(int i=0; i<t.N; i++)
		for(int j=0; j<t.M; j++)
			printf("%d%c",t.m[i][j],j==t.M-1?'\n':' ');
}
int main() {
	Mat a,op;
	int n;
	LL k;
	scanf("%d %lld",&n,&k);
	for(int i=0; i<n; i++) {
		scanf("%d",&a.m[i][0]);
	}
	a.N=n;
	a.M=1;
	op.N=op.M=n;
	for(int i=0; i<op.N; i++)
		for(int j=0; j<op.M; j++)
			if(i==j||(i+1)%n==j)
				op.m[i][j]=1;
			else
				op.m[i][j]=0;
	LL mod=100;
	op=MatPow(op,k,mod);
	Mat res=MatMul(op,a,mod);
	for(int i=0; i<n; i++)
		printf("%d%c",res.m[i][0],i==n-1?'\n':' ');
	return 0;
}

编辑于 2017-08-13 21:44:42 回复(3)
Python
牛客558275203号头像 牛客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)
JacobGo！头像 JacobGo！ 
package go.jacob.day913;

import java.util.Scanner;

/**
 * [编程题]魔力手环
 * 
 * @author Jacob 利用矩阵快速幂求解
 */
public class Demo5 {
	/*
	 * 思路参考：@minnnng 如输入A = [[1, 2, 3]], k = 2。 
	 * 我们可以构造一个这样的矩阵B（代码中的mul矩阵）[[1, 0,
	 * 1], [1, 1, 0], [0, 1, 1]]， 使得A*Bk相当于A转换k次后的样子。
	 *  所以原问题就变成求矩阵快速幂。快速幂取余中，a k
	 * % c =  (a % c)k % c。 类似问题：O(log(n))复杂度的Fibonacci数列，
	 * 
	 */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), k = sc.nextInt();
		// 将arr表示成矩阵而不是数组，是为了方便后续计算
		int[][] arr = new int[n][n];
		for (int i = 0; i < n; i++) {
			arr[0][i] = sc.nextInt();
		}

		// 构造矩阵
		int[][] mat = new int[n][n];

		for (int i = 0; i < n; i++) {
			mat[i][i] = 1;
			// 取模
			mat[(i + 1) % n][i] = 1;
		}
		// 模拟矩阵运算
		for (; k > 0; k >>= 1) {
			//说明最后一位为1，进行右移时会丢失精度
			if ((k & 1) == 1)
				arr = solve(arr, mat);
			mat = solve(mat, mat);
		}
		System.out.print(arr[0][0]);
		for(int i=1;i<arr.length;i++)
			System.out.print(" "+arr[0][i]);
	}

	// 矩阵相乘
	private static int[][] solve(int[][] mat1, int[][] mat2) {
		int n = mat1.length;
		int[][] res = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					if (mat1[i][k] == 0 || mat2[k][j] == 0)
						continue;
					res[i][j] += mat1[i][k] * mat2[k][j];
				}
				if(res[i][j]>=100)
					res[i][j]%=100;
			}
		}
		return res;

	}
}


发表于 2017-09-13 12:12:28 回复(0)
夜小楼Dream头像 夜小楼Dream 
#注意：相同的逻辑java版能过，Python版只能过70%，看来Python还是慢啊
//java版
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int [][] nums = new int[1][55];
		int [][] mat = new int[55][55];
		for(int i=0;i<n;i++){
			nums[0][i] = sc.nextInt();
			mat[i][i] =1;
			mat[(i+1)%n][i] = 1;
		} 
		int [][] ans = multiKMat(nums,mat,k,n);
		
		for(int i=0;i<n-1;i++){
			System.out.print(ans[0][i]+" ");
		}
		System.out.println(ans[0][n-1]);
	}

	private static int[][] multiKMat(int[][] nums, int[][] mat, int k, int n) {
		
		while(k>0){
			if((k&1)==1){
				nums = multiMat(nums,mat,1,n,n);
			}
			mat = multiMat(mat, mat, n, n, n);
			k >>=1;
		}
		return nums;
		
	}

	private static int[][] multiMat(int[][] mat1, int[][] mat2, int n, int m, int q) {
		int [][] res = new int [55][55];
		for(int i=0;i<n;i++ ){
			for(int k=0;k<q;k++){
				for(int j=0;j<m;j++){
					res[i][k] += mat1[i][j] * mat2[j][k];
				}
				res[i][k]%=100;
			}
		}
		return res;
	}
}

-------------------------------------------------------------
#Python版
# -*- coding:utf-8 -*-
import sys

def muliMat(mat1, mat2, n,m,q):
    res= [[0]*q for cn in xrange(n)]
    for i in xrange(n):
        for k in xrange(q):
            for j in xrange(m):
                res[i][k] += mat1[i][j] * mat2[j][k]
            res[i][k] %=100
    return res

def multiKMat(nums,mat, k, n):
    while k :
        if k&1==1:
            nums = muliMat(nums, mat, 1, n, n)
        mat = muliMat(mat,mat,n,n,n)
        k = k>>1
    return nums

if __name__ == '__main__':
    while 1:
        nk = sys.stdin.readline().strip()
        if not nk:
            break
        n,k = [int(i) for i in nk.split(' ')]
        nums = [[int(i) for i in sys.stdin.readline().strip().split( )]]
        mat = [[0]*n for i in xrange(n)]
        for i in xrange(n):
            mat[i][i] =1
            mat[(i+1)%n][i] =1
        ans = multiKMat(nums,mat,k,n)
        print ' '.join(str(x) for x in ans[0])


编辑于 2017-04-09 23:42:00 回复(0)
☠头像 ☠ 
 ### 分析
矩阵快速幂模板题。。。

### 我的答案
```cpp
#include<iostream>
#include<cstring>
using namespace std;
#define MAX 52
#define MOD 100
struct Matrix{
    int n,m;
    int a[MAX][MAX];
    void clear(){
        n=m=0;
        memset(a,0,sizeof a);
    }
    Matrix operator +(const Matrix &b)const{
        Matrix tmp;
        tmp.n=n;
        tmp.m=m;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                tmp.a[i][j]=(a[i][j]+b.a[i][j])%MOD;
        return tmp;
    }
    Matrix operator *(const Matrix &b)const{
        Matrix tmp;
        tmp.clear();
        tmp.n=n;
        tmp.m=b.m;
        for(int i=0;i<n;i++)
            for(int j=0;j<b.m;j++)
                for(int k=0;k<m;k++)
                    tmp.a[i][j]=(tmp.a[i][j]+a[i][k]*b.a[k][j])%MOD;
        return tmp;
    }
    void print()const{
        for(int i=0;i<n;i++){
            for(int j=0;j<m-1;j++)
                cout<<a[i][j]<<" ";
            cout<<a[i][m-1]<<endl;
        }
    }
    Matrix operator ^(int k)const{
        Matrix tmp,mul;
        tmp.clear();
        mul.clear();
        mul.n=mul.m=tmp.m=tmp.n=n;
        mul=mul+(*this);
        for(int i=0;i<n;i++)
            tmp.a[i][i]=1;
        while(k>0){
            if(k&1){
                tmp=tmp*mul;
            }
            k>>=1;
            mul=mul*mul;
        }
        return tmp;
    }
    Matrix transpose(){
        Matrix tmp;
        tmp.n=m;
        tmp.m=n;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                tmp.a[j][i]=a[i][j];
        return tmp;
    }
};
int n,k;
int main(){
    Matrix arr;
    cin>>n>>k;
    arr.m=1;
    arr.n=n;
    for(int i=0;i<n;i++)
        cin>>arr.a[i][0];
    Matrix mul;
    mul.clear();
    mul.n=mul.m=n;
    for(int i=0;i<n;i++){
        mul.a[i][i]=1;
        mul.a[i][(i+1)%n]=1;
    }
    arr=(mul^k)*arr;
    arr.transpose().print();
}
```
 
发表于 2017-03-31 13:12:50 回复(0)
lensh头像 lensh 
#include <stdio.h>
#define N 50
int main(){
	int n,k,i,j;
	int arr[N];
	scanf("%d %d",&n,&k);
	for(i=0;i<n;i++){
		scanf("%d",&arr[i]);
	}
	for(i=0;i<k;i++){
		int temp=arr[0];
		for(j=0;j<n-1;j++){
		    arr[j]+=arr[j+1];
		    if(arr[j]>=100) arr[j]%=100;
		}
		arr[j]+=temp;
	        if(arr[j]>=100) arr[j]%=100;	
	}
	for(i=0;i<n;i++){
		printf("%d",arr[i]);
		if(i<n-1) printf(" ");
	}
	return 0; 
}
不知道为什么这样写时间复杂度太高。。。。。。。不知道还可以怎样优化。。。。求大神支招
发表于 2017-03-29 22:40:33 回复(3)
Lemon502头像 Lemon502 
#include <stdio.h>
#define Max 100

int main ()
{
    int n, k ;
    int a[Max] ;
    int b[Max] ;

    // n表示手环上数字的个数，k表示执行k次变换
    scanf ( "%d %d", &n, &k ) ;

    // 手环初始环
    for ( int i = 0; i < n; i++ ) {
        scanf ( "%d", &a[i] ) ;
    }

    // 处理
    for ( int i = 0; i < k; i++ ) {
　　　　　// 修改数据存储在b数组（如果直接存储在a数组将导致后续数据计算错误）
        for ( int j = 0; j < n; j++ ) {
            b[j%n] = a[j%n] + a[(j+1)%n] ;
            if ( b[j] >= 100 ) {
                b[j] %= 100 ;
            }
        }
        // 重新将数据赋值给a数组
        for ( int j = 0; j < n; j++ ) {
            a[j] = b[j] ;
        }
    }

    // 输出最后的数据信息
    for ( int i = 0; i < n; i++ ) {
        printf ( "%d ", a[i] ) ;
    }

    return 0 ;
}

/* 因为时间复杂度不满足要求，因此导致通过率为60%
 * 希望大家指出改正方法。
 */

发表于 2017-03-25 17:36:47 回复(6)
C/C++
minnnng头像 minnnng
如输入A = [[1, 2, 3]], k = 2。
我们可以构造一个这样的矩阵B（代码中的mul矩阵）[[1, 0, 1], [1, 1, 0], [0, 1, 1]]，使得A*Bk相当于A转换k次后的样子。
于是原问题就变成求矩阵快速幂。快速幂取余中，a k % c =  (a % c)k % c。
类似问题：O(log(n))复杂度的Fibonacci数列， http://blog.csdn.net/dadoneo/article/details/6776272 
#include <bits/stdc++.h>
using namespace std;

class Matrix {
public:
    int n, m;
    vector<vector<int>> mat;
    Matrix(vector<int>& vec) {
        n = 1;
        m = vec.size();
        mat.emplace_back(vec);
    }

    Matrix(int n, int m) : n(n), m(m) {
        mat.resize(n, vector<int>(m, 0));
    }

    Matrix(int n = 0) : n(n), m(n) {
        //构造矩阵B
        mat.resize(n, vector<int>(m, 0));
        for (int i = 0; i < n; ++i) {
            mat[i][i] = 1;
            if (i + 1 < n)
                mat[i+1][i] = 1;
            else
                mat[0][i] = 1;
        }
    }

    Matrix& operator * (Matrix& b) {
        Matrix temp(this->n, b.m);
        if (this->m == b.n) {
            for (int i = 0; i < temp.n; ++i) {
                for (int j = 0; j < temp.m; ++j) {
                    for (int k = 0; k < m; ++k) {
                        temp.mat[i][j] += this->mat[i][k] * b.mat[k][j];
                    }
                }
            }
        }
        *this = temp;
        return *this;
    }

    Matrix& operator % (int k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                this->mat[i][j] %= k;
            }
        }
        return *this;
    }

    void display() {
        for (int i = 0; i < n - 1; ++i) {
            for (int j = 0; j < m - 1; ++j) {
                cout << mat[i][j] << " ";
            }
            cout << mat[i][m-1] << endl;
        }
        for (int i = 0; i < m - 1; ++i) {
            cout << mat[n-1][i] << " ";
        }
        cout << mat[n-1][m-1] << endl;
    }
};

int main() {
    int n, k;
    while (cin >> n >> k) {
        vector<int> vecs(n);
        for (int i = 0; i < n; ++i) {
            cin >> vecs[i];
        }
        Matrix ans(vecs);
        Matrix mul(n);
        while (k != 0) {
            //快速幂求余算法
            if (k & 1) {
                ans = ans * mul % 100;
            }
            mul = mul * mul % 100;
            k >>= 1;
        }
        ans.display();
    }
    return 0;
}
/*intput
7 192347
3 15 7 1 16 1 72
 output
88 72 62 55 11 11 21
 */

编辑于 2017-03-27 02:33:16 回复(1)
Fzldq头像 Fzldq 
# from multiprocessing import cpu_count; print(cpu_count())  # 1 
# 只有1核
def main():
    n, k, *num = map(int, open(0).read().split())
    num = [num]
    mul = [[0] * n for _ in range(n)]
    for i in range(n):
        if i != n - 1:
            mul[i][i] = mul[i + 1][i] = 1
        else:
            mul[i][i] = mul[0][i] = 1

    def multiply(a, b):
        row = len(a)
        res = [[sum(a[i][j] * b[j][k] for j in range(n)) %
                100 for k in range(n)] for i in range(row)]
        return res

    while k:
        if k & 1:
            num = multiply(num, mul)
        mul = multiply(mul, mul)
        k >>= 1
    print(*num[0])


if __name__ == '__main__':
    main()

发表于 2020-07-21 15:48:32 回复(0)
ww_sysu头像 ww_sysu
#include<iostream>
 
#include<vector>
 
#include<map>
 
#include<algorithm>
 
#include<string>
 
#include<cmath>
#include<string>
#include<vector>
 
  
using namespace std;
 
vector<int> number; 
int main()
{
    
    int n, k,temp;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
    cin >> temp;
    number.push_back(temp);
    }
    for(int z=0;z<k;z++)
    {
         
        int unchange = number[0];
        for (int j = 0; j < number.size(); j++)
        {
             
            if (j == number.size() -1)
            
            {
                number[j] = (number[j] + unchange)%100;
                if(z==k-1) cout<<number[j];
            }
            else
             
            {
                number[j] = (number[j] + number[j + 1])%100;
                if(z==k-1) cout<<number[j]<<' ';
            } 
              
        }
  
    }
  
  
          
}
    
发表于 2019-07-18 17:06:42 回复(0)
sisiel头像 sisiel
m=input().split()
num=input().split()
n=int(m[0])
k=int(m[1])
num=[int(x)for x in num]
for j in range(k):
    a=num[0]
    for i in range(n-1):
        num[i]=num[i]+num[i+1]
        if num[i]>100:
            num[i]=num[i]%100
        if i==n-2:
            num[n-1]=num[n-1]+a
            if num[n-1]>100:
                num[n-1]=num[n-1]%100
print(" ".join([str(z) for z in num]))

您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为20.00%
发表于 2018-03-27 16:31:37 回复(0)
lqqqdu头像 lqqqdu 
//矩阵快速幂

import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int [][] array = new int[1][n];//生成二维数组array，1行n列
        for(int i = 0;i < n;i++){
            array[0][i] = scanner.nextInt();
        }
        int [][] mul = new int[n][n]; //生成方程矩阵，n行n列
        for(int i = 0;i < n;i++){
            if(i < n-1){         //如果i<n-1，那么方程矩阵的i列中，i位置及i+1位置为1
                                 //这样array矩阵与mul矩阵相乘，就可以实现当前位置的值+下一个位置的值
                mul[i][i] = 1;
                mul[i+1][i] = 1;
            }
            else {              //边界情况时，array矩阵与mul矩阵相乘，实现当前位置的值+首位置的值
                mul[i][i] = 1;
                mul[0][i] = 1;
            }
        }
        
        for(;k > 0;k = k / 2){  //当k为奇数，则使array与mul矩阵相乘
                                //  k=k/2（同时mul矩阵自乘，从而与k=k/2对应）
                                //当k为偶数，不需要array与mul矩阵相乘，后面的mul矩阵自乘即可
            if(k % 2 == 1){
                array = Core(array,mul);
            }
            mul = Core(mul,mul);
        }
        for(int i = 0;i < n-1;i++){
            System.out.print(array[0][i] + " ");
        }
        System.out.print(array[0][n-1]);   //输出结果
        
    }

    public static int [][] Core(int [][] a,int [][] b){
        int rowResult = a.length;         //结果矩阵的行数 == a矩阵的行数
        int columnResult = b[0].length;   //结果矩阵的列数 == b矩阵的列数
        int columnA = a[0].length;        //a的列数 == b的行数 == k的相加次数
        // a[0].length == b.length
        
        int [][] c = new int [rowResult][columnResult];
        for(int i = 0;i < rowResult;i++){
            for(int j = 0;j < columnResult;j++){
                for(int k = 0;k < columnA;k++){
                    if(a[i][k] == 0 || b[k][j] == 0){//这两者其中一个为0，c[i][j] 都会等于 0
                        continue;   //剪枝           //嫌麻烦或者看不懂这句话也可以不要
                    }
                    c[i][j] += a[i][k] * b[k][j];    //矩阵相乘公式
                }
                // % 100
                if(c[i][j] >= 100){
                    c[i][j] %= 100;
                }
            }
        }
        return c;
    }
}

发表于 2018-03-01 22:08:21 回复(0)
等待offer头像 等待offer
您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为60.00%

//有谁能帮忙指点一下的吗，感谢

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] temp = new int[n];
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for (int i = 0; i < k; i++) {
for (int j = 0; j < n; j++) {
if (j < (n - 1) ) {
temp[j] = (arr[j] + arr[j+1]) % 100;
} else {
temp[j] = (arr[0] + arr[j]) % 100;
}
}
for (int q = 0; q < n; q++) {
arr[q] = temp[q];
}
}
for (int i = 0; i < n; i++) {
System.out.print(arr[i]);
if(i != (n - 1)) {
System.out.print(" ");
}
}
}
}


您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为60.00%
发表于 2017-08-23 16:53:36 回复(0)
C/C++
一纸枫叶头像 一纸枫叶 
清晰易懂，分享给大家。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<vector<int>> matrix_multiply(vector<vector<int>>& arrA, vector<vector<int>>& arrB);

int main() {
	int n, k;
	cin >> n >> k;
	vector<vector<int>> v(n, vector<int>(1, 0));
	vector<vector<int>> vk(n, vector<int>(n, 0));
	for (int i = 0; i < n; ++i) {
		cin >> v[i][0];
	}
	for (int i = 0; i < n; ++i) {
		if (i == n - 1) {
			vk[i][i] = 1;
			vk[i][0] = 1;
			continue;
		}
		vk[i][i] = 1;
		vk[i][i + 1] = 1;
	}
	vector<vector<int>>& res = v;
	while (k > 0) {
		if (k % 2 == 1) {
			v = matrix_multiply(vk, v);
			k--;
		}
		else {
			vk = matrix_multiply(vk, vk);
			k /= 2;
		}
	}
	for(int i = 0; i < res.size(); ++i){
        if(i == res.size() - 1){
            cout << res[i][0] << endl;
            return 0;
        }
        cout << res[i][0] << " ";
    }
}

vector<vector<int>> matrix_multiply(vector<vector<int>>& arrA, vector<vector<int>>& arrB) {
	int rowA = arrA.size();
	int colA = arrA[0].size();
	int rowB = arrB.size();
	int colB = arrB[0].size();
	vector<vector<int>> res;
	if (colA != rowB) {
		return res;
	}
	res.resize(rowA);
	for (int i = 0; i < rowA; ++i) {
		res[i].resize(colB);
	}
	for (int i = 0; i < rowA; ++i) {
		for (int j = 0; j < colB; ++j) {
			for (int k = 0; k < colA; ++k) {
				res[i][j] += arrA[i][k] * arrB[k][j];
			}
            res[i][j] %= 100;
		}
	}
	return res;
}

发表于 2017-08-15 20:26:24 回复(0)
钱塘江头像 钱塘江
用滚动数组 试了好多次 为什么这么简单的代码 复杂度为n*k 只能通过60% 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int k = in.nextInt();
		
		int[][] arr = new int[2][n];
		for(int i = 0; i < n; i++) {
			arr[0][i] = in.nextInt();
		}
		
		int oldflag = 0;
		int flag = 1;
		for(int i = 1; i <= k; i++) {
			flag = i & 1;
			oldflag = (i - 1) & 1;
			
			for(int j = 0; j < n; j++) {
				if(j + 1 == n) 
					arr[flag][j] = arr[oldflag][j] + arr[oldflag][0];
				else
					arr[flag][j] = arr[oldflag][j] + arr[oldflag][j + 1];
                if(arr[flag][j] >= 100 )
					arr[flag][j] %= 100; 
			}
		}
		
		flag = k & 1;
		
		for(int i = 0; i < n - 1; i++) {
			System.out.print(arr[flag][i] + " ");
		}
        
        System.out.println(arr[flag][n-1]);
	}
	
}


发表于 2017-08-10 15:00:07 回复(1)
安安要做程序媛头像 安安要做程序媛 
// 没有人写个js版的，前端狗写个JS的吧。。逻辑参考楼上众位大神给出的矩阵数列。
function cycle (arr, len, k) {
    // init matrix
    var matrix = [], tmpArr = [];
    for (var i = 0; i < len; i++) {
        matrix[i] = [];
        for (var j = 0; j < len; j++) {
            if (i == j || i == j + 1) {
                matrix[i][j] = 1;
            } else {
                matrix[i][j] = 0;
            }
        }
    }
    matrix[0][len - 1] = 1;
    tmpArr[0] = [];

    for (var i = 0; i < len; i++) {
        tmpArr[0][i] = arr[i];
    }
    var ans = multiKMat(tmpArr, matrix, k, len);
    console.log(ans[0].join(' '));
}

function multiKMat (tmpArr, matrix, k, n) {
    while (k > 0) {            
        if ((k & 1) == 1) {                
            tmpArr = multiMat(tmpArr, matrix, 1, n, n);            
        }            
        matrix = multiMat(matrix, matrix, n, n, n);
        k >>= 1;        
    }  
    return tmpArr; 
}

function multiMat (matrix1, matrix2, n, m, q) {
    var res = [];        
    for (var i = 0; i < n; i++) { 
        res[i] = [];           
        for (var k = 0; k < q; k++) {
            res[i][k] = 0;                
            for (var j = 0; j < m; j++) {                    
                res[i][k] += matrix1[i][j] * matrix2[j][k];
            }                
            res[i][k] %= 100;  
        }        
    }  
    return res;  
}

// 其实我本来是这样写的=-=，然而，超时了。 
function cycle (arr, len, k) {
    var tmp = [];
    for (var i = 0; i < k; i++) {
        // cycle 1st
        for (var j = 0; j < len; j++) {
            if (j != len - 1) {
                tmp[j] = arr[j] + arr[j + 1];
                if (tmp[j] >= 100) {
                    tmp[j] = tmp[j] % 100;
                }
            } else {
                tmp[j] = arr[j] + arr[0];
                if (tmp[j] >= 100) {
                    tmp[j] = tmp[j] % 100;
                }
            }
        }
        arr = [].concat(tmp);
    }
    return arr;
}

发表于 2017-08-09 12:19:53 回复(0)
Java
朱大葱头像 朱大葱 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            long[] array = new long[n];
            for (int i = 0; i <n ; i++) {
                array[i] = scanner.nextInt();
            }
            for (int i = 0; i < k ; i++) {
                long temp =array[0];
                for (int j = 0; j < n; j++) {
                    if (array[j]>=100){
                        array[j]%=100;
                    }

                    if(j==n-1){
                        array[j] = (array[j]+temp%100)%100;
                    }else{
                        array[j] = (array[j]+array[(j+1)%n]%100)%100;
                    }
                }
            }
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i]);
                if (i!=array.length-1){
                    System.out.print(" ");
                }
            }
        }
    }
}
您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为60.00%
尴尬!!!

发表于 2017-08-02 14:57:04 回复(0)
提交观点

问题信息

动态规划
来自：网易2017春招笔试真...
难度：
39条回答 11919浏览

热门推荐

通过挑战的用户

相关试题

魔力手环

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号