Matrix matMul(Matrix a ,Matrix b,int n)
{
      Matrix c;
      memset(c.mat,0,sizeof(c.mat));
      int i,j,k;
      for (k = 1; k<=n ; k++)
          for (i=1 ;i<=n ; i++)
              if(a.mat[i][k])
                   for (j = 1 ;j<=n ;j++)
                      c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MODNUM;
      return c;
}
Matrix quickMatPow(Matrix a ,int b ,int n) // n阶矩阵a快速b次幂
{
      Matrix c;
      memset(c.mat ,0 ,sizeof(c.mat));
      int i;
      for (i = 1 ;i <= n ;i++)
          c.mat[i][i] = 1;
      while(b)
      {
            if (b & 1)
                c = matMul(c ,a ,n); // c=c*a;
            a = matMul(a ,a ,n); // a=a*a
            b /= 2;
      }
      return c;
}
int main()
{
      int k,n,i,sum;
      int a[110] ,b[110]; 
      Matrix start ,ans;
      while (scanf("%d" ,&k) && k!=0)
      {
            for (i = 0 ;i < k ;i ++)
                 scanf("%d" ,&a[i]);
            for (i = 1 ;i <=k ;i ++)
                 scanf("%d" ,&b[i]);
            scanf("%d" ,&n);
            if (n<k)
            {
                 printf("%d\n" ,a[n]);
                 continue;
            }
            memset(start.mat ,0 ,sizeof(start.mat));
            for (i = 1 ;i < k ;i ++)
                 start.mat[i][i+1] = 1;
            for (i = 1 ;i <= k ;i ++)
                 start.mat[k][i] = b[k-i+1];
            ans = quickMatPow(start ,n-k+1,k);
            sum = 0;
            for(i = 1 ;i <= k ;i++)
                  sum = (sum + a[i-1] * ans.mat[k][i]) % MODNUM;
            printf("%d\n" ,sum);
      }
      return 0;
}

【例4】简单定义的函数F(x)。 

       设函数f(x)的定义如下：

              f(x) = x    (x < 10)

              f(x) = a0 * f(x-1) + a1 * f(x-2) + …… + a9 * f(x-10)   (x >= 10)