A Simple Math Problem
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2547 Accepted Submission(s): 1485
Problem Description
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.
Input
The problem contains mutiple test cases.Please process to the end of file.
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.
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.
Output
For each case, output f(k) % m in one line.
Sample Input
10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0
Sample Output
45
104
题意:
给出 k( < 2 X 10 ^ 9) 和 m( < 10 ^ 5),数列的规则:
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(k)%m 。
思路:
矩阵快速幂。根据式子可以得出:
化简后可以得出 :
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef vector<int> vec; typedef vector<vec> met; met mul (met a, met b, int mod) { met c(a.size(), vec(b[0].size())); for (int i = 0; i < a.size(); ++i) { for (int j = 0; j < b[0].size(); ++j) { for (int k = 0; k < b.size(); ++k) { c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod; } } } return c; } met pow (met a, int n, int mod) { met b(a.size(), vec(a[0].size())); for (int i = 0; i < a.size(); ++i) { b[i][i] = 1; } while (n > 0) { if (n & 1) b = mul(b, a, mod); a = mul(a, a, mod); n >>= 1; } return b; } int main () { int k, mod; while (~scanf("%d%d", &k, &mod)) { met a(10, vec(10)); for (int i = 0; i < a[0].size(); ++i) scanf("%d", &a[0][i]); for (int i = 1; i < a.size(); ++i) a[i][i - 1] = 1; if (k >= 10) { int sum = 0; a = pow(a, k - 9, mod); for (int i = 0; i < 10; ++i) { sum = (sum + a[0][i] * (9 - i)) % mod; } printf("%d\n", sum % mod); } else printf("%d\n", k % mod); } return 0; }
相关推荐
Simple DP Problem:数塔问题
Simple Math Game Application with SQLite in Python
A Simple Mesh Generator in MATLABA Simple Mesh Generator in MATLABA Simple Mesh Generator in MATLABA Simple Mesh Generator in MATLAB
JavaScript
JavaScript
Dropout:A Simple Way to Prevent Neural Networks from Overfitting.zip
A simple echo Server
We want to offer a short and simple MATLAB code, described in more detail than usual, so the reader can experiment (and add to the code) knowing the underlying principles. We find the node locations ...
WATCH THE UNOBSERVED_ A SIMPLE APPROACH TO PARALLELIZING
A simple calculator program.
标签:airavata-simple-math-service-0.8.jar,airavata,simple,math,service,0.8,jar包下载,依赖包
标签:airavata-simple-math-service-0.10.jar,airavata,simple,math,service,0.10,jar包下载,依赖包
标签:airavata-simple-math-service-0.6.jar,airavata,simple,math,service,0.6,jar包下载,依赖包
标签:airavata-simple-math-service-0.11.jar,airavata,simple,math,service,0.11,jar包下载,依赖包
标签:airavata-simple-math-service-0.7.jar,airavata,simple,math,service,0.7,jar包下载,依赖包
标签:airavata-simple-math-service-0.5.jar,airavata,simple,math,service,0.5,jar包下载,依赖包
一阶差分麦克风 差分麦克风 自适应 差分麦克风 自适应 差分麦克风 自适应 差分麦克风 自适应
标签:airavata-simple-math-service-0.9.jar,airavata,simple,math,service,0.9,jar包下载,依赖包
A simple airline ticket reservation program 英文题目,里面有,代码是上课我自己交的
simple-sharding, ☕️ A simple database shard middleware.zip