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.
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.
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
题意:给出两个式子求f(k)%m.
题解:根据第二个式子是递推式,可以根据这种类型的递推式发现这是一个矩阵快速幂的题目,那就是要构造矩阵了。怎么构造呢? 根据第二个递推式发现 :
f(x-1) a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 f(x)
f(x-2) 1 0 0 0 0 0 0 0 0 0 f(x-1)
f(x-3) 0 1 0 0 0 0 0 0 0 0 f(x-2)
f(x-4) 0 0 1 0 0 0 0 0 0 0 f(x-3)
f(x-5) 0 0 0 1 0 0 0 0 0 0 f(x-4)
f(x-6) 0 0 0 0 1 0 0 0 0 0 f(x-5)
f(x-7) 0 0 0 0 0 1 0 0 0 0 f(x-6)
f(x-8) 0 0 0 0 0 0 1 0 0 0 f(x-7)
f(x-9) 0 0 0 0 0 0 0 1 0 0 f(x-8)
f(x-10) 0 0 0 0 0 0 0 0 1 0 f(x-9)
其中红色部分为我们构造出来的矩阵,求出构造矩阵的k-10+1次方,用第一行对应乘以9,8,7,6,5,4,3,2,1,0然后相加,就是结果了。详细请看代码。
C++:
#include <iostream>
#include <cstring>
using namespace std;
struct hh{
int a[20][20];
}x;// 储存构造矩阵以及经过运算得出来的矩阵
int q[10]={9,8,7,6,5,4,3,2,1,0};
hh mul(hh x,hh y,int c){//矩阵快速幂
hh w;
memset(w.a,0,sizeof(w.a));
for (int i = 0; i < 10;i++){
for (int j = 0; j < 10;j++){
for (int k = 0; k < 10;k++){
w.a[i][j]=(w.a[i][j]%c+(x.a[i][k]%c*y.a[k][j]%c)%c)%c;
}
}
}
return w;
}
hh j_quick(hh a,int b,int c){//矩阵快速幂
hh ans;
memset(ans.a,0,sizeof(ans.a));
for (int i = 0; i < 10;i++){
ans.a[i][i]=1;
}
while(b!=0){
if(b&1) ans=mul(ans,a,c);
b>>=1;
a=mul(a,a,c);
}
return ans;
}
int main(){
memset(x.a,0,sizeof(x.a));
int k,m;
while(cin >> k >> m){
for (int i = 0; i < 10;i++){
cin >> x.a[0][i];
if(i<9)
x.a[i+1][i]=1;
}// 输入构造矩阵
hh z=j_quick(x,k-10+1,m);// 计算构造矩阵的k-10+1次方
int sum=0;
for (int i = 0; i < 10;i++){// 计算最终矩阵第一行与9,8,7,6,5,4,3,2,1,0的乘积加和
sum=(sum%m+(z.a[0][i]%m*q[i]%m)%m)%m;
}
cout << sum << endl;
}
return 0;
}
我写的这个没有考虑k小于10的情况,很迷,但是过了。大家可以自己加上。留个就当是小作业吧。。。。嘻嘻~~~
java:这个考虑k小于10的情况了。
import java.util.*;
public class Main {
static Scanner cin = new Scanner(System.in);
static int k,m;
static long ww[];
static class hh{
long [][] a = new long [11][11];
public hh() {
for (int i = 0; i < 10;i++) {
for (int j = 1; j < 10;j++) {
a[i][j]=0;
}
}
}
}
static hh mul(hh aa,hh b,long x) {
hh c = new hh();
for (int i = 0; i < 10;i++) {
for (int j = 0; j < 10;j++) {
for (int k = 0; k < 10;k++) {
c.a[i][j]=(c.a[i][j]+aa.a[i][k]*b.a[k][j]%x)%x;
}
}
}
return c;
}
static hh quick(hh x,long y,long c) {
hh ans = new hh();
for (int i = 0; i < 10;i++) ans.a[i][i]=1;
while(y!=0) {
if(y%2==1) ans=mul(ans,x,c);
y>>=1;
x=mul(x,x,c);
}
return ans;
}
public static void main(String[] args){
ww = new long [15];
while(cin.hasNext()) {
k = cin.nextInt();
m=cin.nextInt();
hh a = new hh();
for (int i = 0; i < 10;i++) {
ww[i]=cin.nextLong();
}
for (int i = 0; i < 10;i++) {
a.a[0][i]=ww[i];
if(i>=1) a.a[i][i-1]=1;
}
if(k<=9) {
System.out.println(ww[k]%m);
}
else {
a=quick(a,k-9,m);
long sum=0;
for (int i = 0; i < 10;i++) {
sum=sum%m+((9-i)*a.a[0][i]%m)%m;
}
System.out.println(sum%m);
}
}
}
}