本文主要是介绍HDU-1757（矩阵快速幂），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Lele now is thinking about a simple function f(x).
If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .
Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.
If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .
Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.
10 9999 1 1 1 1 1 1 1 1 1 1 20 500 1 0 1 0 1 0 1 0 1 0
45 104
/*
题意：给两个数k和m，然后是10个由0和1组成的数，分别代表a0->a9，求f（k）%m
f（x）定义为：
If x < 10 ，f(x) = x.
If x >= 10 ，f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);题解：
构建矩阵
| f(10)| |a0 a1 a2 ...a8 a9| |f(9)|
| f(9) | | 1 0 0 ... 0 0| |f(8)|
| .....| = |.. ... ... ... ..| * | .. |
| f(2) | | 0 0 0 ... 0 0| |f(1)|
| f(1) | | 0 0 0 ... 1 0| |f(0)|*/#include <stdio.h>
#include <string.h>
#include<iostream>
#include <algorithm>
#include<math.h>
#include<map>
using namespace std;struct node
{int maxtri[12][12];
};
node res, roi;
long long int k, m;void init()
{memset(res.maxtri, 0, sizeof(res.maxtri));for (int i = 0; i < 10; i++){res.maxtri[i][i] = 1;}for (int i = 1; i < 10; i++){for (int j = 0; j < 10; j++){if ((i - 1) == j){roi.maxtri[i][j] = 1;}elseroi.maxtri[i][j] = 0;}}
}node muti(node ss, node tt)
{node ans;memset(ans.maxtri, 0, sizeof(ans.maxtri));for (int i = 0; i < 10; i++){for (int j = 0; j < 10; j++){if (ss.maxtri[i][j] == 0)continue;for (int kk = 0; kk < 10; kk++){ans.maxtri[i][kk] = (ans.maxtri[i][kk] + (ss.maxtri[i][j] * tt.maxtri[j][kk]) % m) % m;}}}return ans;
}void muti_maxtri(int n)
{while (n){if (n % 2 != 0){res = muti(res, roi);}roi = muti(roi, roi);n /= 2;}}int main()
{while (cin >> k >> m){for (int i = 0; i < 10; i++){cin >> roi.maxtri[0][i];}init();if (k <= 9){cout << k%m << endl;continue;}else{muti_maxtri(k - 9);int sum = 0;for (int i = 0; i < 10; i++){sum += (res.maxtri[0][i] * (9 - i)) % m;sum %= m;}cout << sum << endl;}}return 0;
}
这篇关于HDU-1757（矩阵快速幂）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
