题目链接：https://vjudge.net/problem/UVA-10870
题目意思：
给出a1，a2，a3，a4，a5………………ad，然后算下面这个递推式子，简单的矩阵快速幂，裸题，但是第一个次遇到了矩阵大小不确定的矩阵快速幂，而且在这道题里面第一次明白了如何构造矩阵。算是矩阵快速幂的学习的一个小里程碑吧。
f(n) = a1 ＊f(n - 1) + a2 ＊f(n - 2) + a3 ＊f(n - 3) + … + ad＊ f(n - d), n > d.求f(n)
代码：
1 //Author: xiaowuga 2 #include <bits/stdc++.h> 3 #define maxx INT_MAX 4 #define minn INT_MIN 5 #define inf 0x3f3f3f3f 6 using namespace std; 7 typedef long long ll; 8 ll n; 9 ll MOD; 10 struct Matrix{ 11 ll mat[101][101]; 12 void clear(){ 13 memset(mat,0,sizeof(mat)); 14 } 15 Matrix operator * (const Matrix & m) const{ 16 Matrix tmp; 17 tmp.clear(); 18 for(int i=0;i<n;i++) 19 for(int k=0;k<n;k++){ 20 if(mat[i][k]==0) continue; 21 for(int j=0;j<n;j++){ 22 tmp.mat[i][j]+=mat[i][k]*m.mat[k][j]%MOD; 23 tmp.mat[i][j]%=MOD; 24 } 25 } 26 return tmp; 27 } 28 }; 29 Matrix POW(Matrix &m,int k){ 30 Matrix ans; 31 memset(ans.mat,0,sizeof(ans.mat)); 32 for(int i=0;i<n;i++) ans.mat[i][i]=1; 33 while(k){ 34 if(k&1) ans=ans*m; 35 k/=2; 36 m=m*m; 37 } 38 return ans; 39 } 40 int main() { 41 ios::sync_with_stdio(false);cin.tie(0); 42 int T; 43 while(cin>>n>>T>>MOD&&n&&T&&MOD){ 44 Matrix m; 45 m.clear(); 46 for(int i=0;i<n;i++){ 47 cin>>m.mat[0][i]; 48 m.mat[0][i]%=MOD; 49 } 50 ll f[101]; 51 for(int i=0;i<n;i++){ 52 cin>>f[i]; 53 } 54 for(int i=1;i<n;i++){ 55 m.mat[i][i-1]=1; 56 } 57 Matrix ans=POW(m,T-n); 58 ll sum=0; 59 for(int i=0;i<n;i++){ 60 sum=sum+ans.mat[0][i]*f[n-1-i]%MOD; 61 sum%=MOD; 62 } 63 cout<<sum<<endl; 64 } 65 return 0; 66 }