[编程题]魔力手环
- 热度指数：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
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的
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)
#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)
构造矩阵，然后使用矩阵快速幂即可
时间复杂度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)
矩阵快速乘的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)
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)
#注意：相同的逻辑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)
#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)
#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)
如输入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)
# 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)
#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]<<' ';
}
}
}
}
#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)
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
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%
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为20.00%
发表于 2018-03-27 16:31:37
回复(0)
//矩阵快速幂
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)
您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为60.00%
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
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%
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为60.00%
发表于 2017-08-23 16:53:36
回复(0)
清晰易懂，分享给大家。
#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)
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)
问题信息
通过挑战的用户
相关试题
-
评论(79) 来自网易2017春招笔试真题...
-
评论(153) 来自网易2017春招笔试真题...
-
评论(79) 来自网易2017春招笔试真题...
-
评论(57) 来自网易2017春招笔试真题...
-
评论(43) 来自网易2017春招笔试真题...
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
