魔力手环

2023-11-01 22:38

文章标签 魔力手环

本文主要是介绍魔力手环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

小易拥有一个拥有魔力的手环上面有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

过了50%的数据的代码，内存超了，据说要用矩阵快速幂做才行

#include"iostream"
#include<map>
using namespace std;int main()
{int n,k;int ai[60];int bi[60];cin>>n>>k;map<string,int> jj;for(int i=0;i<n;i++){cin>>ai[i];bi[i]=ai[i];}int xun;int qi;int it;for(it=1;it<=k;it++){string biaoji;for(int i=0;i<n;i++){int a=bi[i];while(a){int ge=a%10;a=a/10;char b=ge+'0';biaoji+=b;}//biaoji+='-';}if(!jj[biaoji]){jj[biaoji]=it;}else{qi=jj[biaoji];xun=it-jj[biaoji];break;}int beg=bi[0];for(int i=0;i<n-1;i++){bi[i]+=bi[i+1];bi[i]%=100;}bi[n-1]=(bi[n-1]+beg)%100;}int wei=k;if(it<k){wei=(k-qi)%xun+qi;}cout<<xun+qi<<endl;while(wei--){int beg=ai[0];for(int i=0;i<n-1;i++){ai[i]+=ai[i+1];ai[i]%=100;}ai[n-1]=(ai[n-1]+beg)%100;}for(int i=0;i<n-1;i++)cout<<ai[i]<<" ";cout<<ai[n-1]<<endl;return 0;
}