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

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

Program:

#include#define MAXN 110using 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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。