首页 > 代码库 > 魔力手环(快速幂求解)
魔力手环(快速幂求解)
题目链接:https://www.nowcoder.com/questionTerminal/79c639e02bc94e6b919e3372c8e1dc5e
小易拥有一个拥有魔力的手环上面有n个数字(构成一个环),当这个魔力手环每次使用魔力的时候就会发生一种奇特的变化:每个数字会变成自己跟后面一个数字的和(最后一个数字的后面一个数字是第一个),一旦某个位置的数字大于等于100就马上对100取模(比如某个位置变为103,就会自动变为3).现在给出这个魔力手环的构成,请你计算出使用k次魔力之后魔力手环的状态。
输入描述:
输入数据包括两行: 第一行为两个整数n(2 ≤ n ≤ 50)和k(1 ≤ k ≤ 2000000000),以空格分隔 第二行为魔力手环初始的n个数,以空格分隔。范围都在0至99.
输出描述:
输出魔力手环使用k次之后的状态,以空格分隔,行末无空格。
输入例子:
3 2 1 2 3
输出例子:
8 9 7
思路:n个数的环进行移动相加,考虑到矩阵行、列变换可以完成这种移动和相加,于是构造出快速幂矩阵,快速幂矩阵M和原矩阵S相乘得到一次移动的结果,那么F(n+1) = M^n*S(这里的幂和乘法是矩阵的运算),很容易得到如下递推示例:
[[1 1 0] [0 1 1] [1 0 1]]*[[a][b][c]] = [[a+b][b+c][c+a]], 如此,已经确定了快速幂矩阵M,那么就要考虑如何相乘得到最快的幂求解速度。建议参看这篇博客
代码如下:(算法复杂度为O(n^3*log(k)))
#include<iostream> #include<cstring> using namespace std; int main(){ int n,k; cin >> n >> k; int d[n];//存放结果 for(int i=0;i<n;++i) { cin >> d[i]; } //构造快速幂矩阵 int Mul[n][n]; for(int i=0;i<n-1;++i) { fill(Mul[i],Mul[i]+n,0); Mul[i][i] = 1; Mul[i][i+1] = 1; } fill(Mul[n-1],Mul[n-1]+n,0); Mul[n-1][0] = 1; Mul[n-1][n-1] = 1; //转化为2进制,进行二分搜索 while(k) { if(k&1) { int temp[n]; fill(temp, temp+n, 0); for(int i=0;i<n;++i) { for(int j=0;j<n;++j) { temp[i] += (Mul[i][j]*d[j]); temp[i] = temp[i]%100; } } memcpy(d, temp, sizeof(d)); } k = k>>1; int temp[n][n]; for(int i=0;i<n;++i) { fill(temp[i],temp[i]+n,0); } for(int i=0;i<n;++i) { for(int j=0;j<n;++j) { for(int k=0;k<n;++k) { temp[i][j]+=Mul[i][k]*Mul[k][j];//二维矩阵相乘 } temp[i][j] %= 100;//快速幂取余中,a^k % c = (a % c)^k % c } } for(int i=0;i<n;++i) { memcpy(Mul[i],temp[i],sizeof(Mul[i])); } } //输出结果 for(int i=0;i<n-1;++i) { cout << d[i] << ‘ ‘; } cout << d[n-1] << endl; return 0; }
矩阵快速幂的总结(更多问题->熟练掌握)
魔力手环(快速幂求解)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。