POJ - 2118 矩阵乘法来解线性递推

来源：恒创科技编辑：恒创科技编辑部

2024-02-02 09:40:59

看了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 就用二分的方法~~多大的数都轻轻松松啊~~

Program:

#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;   
}