如果有相应的OJ题目,欢迎同学们提供相应的链接
相关链接
简单的测试
None
代码模板
/*
* TIME COMPLEXITY:O(n^3log(t))
* PARAMS:
* a The constant array.
* b The initial array.
* n The length of array.
* t The iterator's value.
*
* MATRIX M:
* 0 1 0 ... 0
* 0 0 1 ... 0
* ... ... ...
* 0 0 0 ... 1
* a[n-1] a[n-2] a[n-3] ... a[0] But,here we use M.a[last row][i]=a[i],so inverse a before you call this function.
*
* MATRIX F
* b[0]
* b[1]
* .
* .
* .
* b[n] As we call M*F,the first row will gone and insert a new b[n+1]=M.a[last_row]*F.a[first_column] at the last row position.Until t is reached.
*/
int solve(int a[],int b[],int n,int t){
Matrix M,F,E;
M.clear(),F.clear(),E.clear();
M.n=M.m=n;
E.n=E.m=n;
F.n=n,F.m=1;
for(int i=0;i<n-1;i++)
M.a[i][i+1]=1;
for(int i=0;i<n;i++){
//notice:Maybe,first you should inverse a array before you call this function.
M.a[n-1][i]=a[i];
F.a[i][0]=b[i];
E.a[i][i]=1;
}
if(t<n)
return F.a[t][0];
//Here is fast Exponentiation.
for(t-=n-1;t;t/=2){
if(t&1)
E=M*E;
M=M*M;
}
F=E*F;
return F.a[n-1][0];
}