2017网易实习生招聘编程题之魔力手环(矩阵幂)

网易实习生招聘编程题之魔力手环(矩阵幂)"/>

2017网易实习生招聘编程题之魔力手环(矩阵幂)

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

分析：对于题目例子中的输入3 2， (1,2,3)每经过一次变换相当于乘以一个3*3的矩阵 A:
1 0 1
1 1 0
0 1 1
那么，k=2，就相当于乘以 A2 $A^{2}$，最后输出结果相当于 输入的值乘以矩阵 Ak $A^{k}$，我们又知道(a+b)%100=(a%100+b%100)%100， 故这道题实际上就相当于求矩阵的幂。

那么怎么快速求矩阵的幂呢？可以通过这个公式：
Ak=Ak/2∗Ak/2 $A^{k}=A^{k/2}*A^{k/2}$ (如果k是偶数)
Ak=Ak−1∗A $A^{k}=A^{k-1}*A$ (如果k是奇数)
我们只需要递归，就可以很容易的通过这个公式求矩阵的幂了。
废话不多说，直接上代码：

//网易春招笔试17_5  魔力手环    (a+b)%100=(a%100+b%100)%100
#include<iostream>
#include<vector>
using namespace std; 
void matrixMultiply(int a[50][50],int b[50][50],int c[50][50],int n)  // 求矩阵c=a*b
{
    int i,j,k;
    int d[50][50];
    memset(d,0,sizeof(int)*2500);
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            for(k=0;k<n;k++)
            {
                d[i][j]=(d[i][j]+a[i][k]*b[k][j])%100;
            }
        }
    }
    memcpy(c,d,sizeof(d));
}
void moli(int a[50][50],int b[50][50],int n,int k)  //数组(矩阵)为a[n][n]，求b=a^k(矩阵a的k次幂)
{
    if(k==0)
    {
        memset(b,0,sizeof(int)*2500);
        for(int i=0;i<n;i++)   //将矩阵b赋值为单位矩阵
            b[i][i]=1;
        return;
    }
    else if(k%2==0)
    {
        moli(a,b,n,k/2);
        matrixMultiply(b,b,b,n);
    }
    else
    {
        moli(a,b,n,k-1);
        matrixMultiply(a,b,b,n);
    }
}
int main()
{
    int n,k,i,j;
    cin>>n>>k;
    int c[50]={0},d[50]={0};
    int a[50][50],b[50][50];
    for(i=0;i<n;i++)
    {
        cin>>c[i];
    }
    memset(a,0,sizeof(int)*2500);
    memset(b,0,sizeof(int)*2500);
    for(i=0;i<n;i++)   //求输入的数所对应的矩阵
    {
        a[i][i]=1;
        a[(i+1)%n][i]=1;
    }
    moli(a,b,n,k);        //求矩阵b，b=a^k
    memset(d,0,sizeof(d));
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            d[i]=(d[i]+c[j]*b[j][i])%100;
        }
    }
    for(i=0;i<n;i++)
        cout<<d[i]<<" ";
    cout<<endl;
    return 0;
}