POJ - 2118 矩陣乘法來解線性遞推

    看了Matrix67關于Fibonacci那段的講解...就和狐狸大牛一起去POJ做了這道...我了個去我了個擦...600多個人做200多個過真的大丈夫？？第一次做這種這麼少人做的題很是緊張...囧... 

    其實了解了用矩陣來解線性遞推的方法...這題...模闆題...記住幾個關鍵...用矩陣乘法來解線性遞推，首先當然是構造矩陣A..這個矩陣該有的性質是乘以

   {    a1                            {    a2 

        a2                                  a3                

        a3  }   能使其變成        a4  }  之類的..也就使 a 每乘一個A..a這一列往後面滾一個...是以如果要求第 n 項...實際就是求 ( A^(n-k) ) * a 這裡k是指的 a 的列數也就是線性遞推時右邊的未知數....一開始是把 1 ~ k  存在裡面了（不給出初值沒法做~~） .. 是以當 n <=k 時直接輸出...大于 k 時才看是乘 A....           

     求A^k 就用二分的方法~~多大的數都輕輕松松啊~~

#include<iostream>
#define MAXN 110
using namespace std;
struct pp
{
   int s[MAXN][MAXN];      
}a;
int n,i,s[MAXN],ans=0;
pp muti(pp a,pp b)
{
    int i,j,k;
    pp h;   
    for (i=1;i<=n;i++)
       for (j=1;j<=n;j++)
       {
           h.s[i][j]=0;
           for (k=1;k<=n;k++)
              h.s[i][j]+=(a.s[i][k]*b.s[k][j])%10000;
           h.s[i][j]%=10000;
       }
    return h;       
}
pp find(int p)
{
    pp h;
    if (p==1) return a;
    h=find(p/2);
    h=muti(h,h);
    if (p%2) h=muti(h,a);
    return h;           
}
int main()
{ 
    while (~scanf("%d",&n))
    {
         if (!n) break;
         for (i=1;i<=n;i++) scanf("%d",&s[i]);         
         memset(a.s,0,sizeof(a.s));
         for (i=1;i<n;i++) a.s[i][i+1]=1;      
         for (i=1;i<=n;i++) scanf("%d",&a.s[n][n-i+1]);
         scanf("%d",&i);  i++;
         if (i<=n) ans=s[i];
         else
         {
             i-=n;
             ans=0;
             a=find(i);
             for (i=1;i<=n;i++) ans+=(s[i]*a.s[n][i])%10000;
         }
         ans%=10000;
         printf("%d\n",ans);
    }
    return 0;   
}