小易拥有一个拥有魔力的手环上面有n个数字(构成一个环),当这个魔力手环每次使用魔力的时候就会发生一种奇特的变化：每个数字会变成自己跟后面一个数字的和(最后一个数字的后面一个数字是第一个),一旦某个位置的数字大于等于100就马上对100取模(比如某个位置变为103,就会自动变为3).现在给出这个魔力手环的构成，请你计算出使用k次魔力之后魔力手环的状态。
输入数据包括两行： 第一行为两个整数n(2 ≤ n ≤ 50)和k(1 ≤ k ≤ 2000000000),以空格分隔 第二行为魔力手环初始的n个数，以空格分隔。范围都在0至99. 输出魔力手环使用k次之后的状态，以空格分隔，行末无空格。 若直接采用递推公式计算，运算量很大，会提示超时，本题宜采用快速矩阵幂进行计算，代码如下： #include<iostream> using namespace std; int ** mulMatrix(int **a, int **b, int n) { int **res = new int*[n]; for (int i = 0; i<n; i++) { res[i] = new int[n]; } for (int i = 0; i<n; i++) { for (int j = 0; j<n; j++) { res[i][j] = 0; for (int k = 0; k<n; k++) { res[i][j] += a[i][k]*b[k][j]; } res[i][j] = res[i][j] % 100; } } return res; } int main() { int n, k; cin >> n >> k; int arr[50] = { 0 }; for (int i = 0; i<n;i++) { cin >> arr[i]; } int **initMatrix = new int*[n]; for (int i = 0; i<n; i++) { initMatrix[i] = new int[n]; } for (int i = 0; i<n; i++) { for (int j = 0; j<n; j++) { initMatrix[i][j] = 0; } } for (int i = 0; i<n - 1; i++) { initMatrix[i][i] = 1; initMatrix[i][i + 1] = 1; } initMatrix[n - 1][0] = 1; initMatrix[n - 1][n - 1] = 1; int **resMatrix = new int*[n]; for (int i = 0; i<n; i++) { resMatrix[i] = new int[n]; } for (int i = 0; i<n; i++) { for (int j = 0; j<n; j++) { if (i == j) { resMatrix[i][j] = 1; } else { resMatrix[i][j] = 0; } } } while (k != 0) { if (k % 2 == 1) { resMatrix = mulMatrix(resMatrix, initMatrix, n); } initMatrix = mulMatrix(initMatrix, initMatrix, n); k = k >> 1; } int res[50] = { 0 }; for (int i = 0; i<n; i++) { for (int j = 0; j<n; j++) { res[i] += resMatrix[i][j] * arr[j]; } res[i] = res[i] % 100; } for (int i = 0; i<n - 1; i++) { cout << res[i] << " "; } cout << res[n - 1]; return 0; }