矩阵链乘+斐波那契+快速幂 专题

http://acm.hdu.edu.cn/showproblem.php?pid=3117

Fibonacci Numbers

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1093    Accepted Submission(s): 469

Problem Description
What is the numerical value of the nth Fibonacci number? InputSample InputSample OutputSourceRecommend#include <cstdio>#include<iostream>#include<cstdlib>#include<stdio.h>#include<math.h>using namespace std;int f[40];const int MAX = 2;typedef struct{int m[MAX][MAX];} Matrix;Matrix P ={1,1,1,0};Matrix I ={1,0,0,1};Matrix matrixmul(Matrix a,Matrix b) //矩阵乘法{int i,j,k;Matrix c;for (i = 0 ; i < MAX; i++)for (j = 0; j < MAX;j++){c.m[i][j] = 0;for (k = 0; k < MAX; k++)c.m[i][j] += (a.m[i][k] * b.m[k][j])%10000;c.m[i][j] %= 10000;}return c;}Matrix quickpow(int n){Matrix m = P, b = I;while (n >= 1){if (n & 1)b = matrixmul(b,m);n = n >> 1;m = matrixmul(m,m);}return b;}void pre(int n){ double a=sqrt(5.0); double b=(sqrt(5.0)+1)/2; double s=log(1.0/a)/log(10.0)+n*log(b)/log(10.0); double t=s-(int)s+3; double f=pow(10.0,t); f=(int)f; cout<<f<<"...";}void bb(int n){ Matrix g=quickpow(n-1); int h=g.m[0][0]*1%10000; printf("%04d\n",h);}int main(){ int n; f[0]=0;f[1]=1; for(int i=2;i<40;i++) f[i]=f[i-1]+f[i-2]; while(scanf("%lld",&n)!=EOF) { if(n<40){cout<<f[n]<<endl;continue;} pre(n); bb(n); }}

 http://acm.hdu.edu.cn/showproblem.php?pid=1588

Gauss Fibonacci

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1425    Accepted Submission(s): 622

Problem DescriptionInputOutputSample InputSample OutputAuthorSourceRecommend#include<iostream>#include<stdio.h>#define ll long longusing namespace std;struct Node{ll mat[2][2];};const int n=2;int k,b,nn,m;Node unit,qiqi;Node mul(const Node &a,const Node &b){Node c;int i,j,k;for(i=0;i<n;i++)for(j=0;j<n;j++){c.mat[i][j]=0;for(k=0;k<n;k++)c.mat[i][j]+=(a.mat[i][k]*b.mat[k][j])%m;c.mat[i][j]%=m;}return c;}Node power(const Node &a,int x){int i,j;int t=x,d=0;while(t)d++,t>>=1;Node res=unit;for(i=d;i>0;i--){res=mul(res,res);if(x&(1<<(i-1)))res=mul(res,a);}return res;}Node add(const Node &a,const Node &b){Node c;int i,j;for(i=0;i<n;i++)for(j=0;j<n;j++)c.mat[i][j]=(a.mat[i][j]+b.mat[i][j])%m;return c;}Node sum(const Node &a,int x)//A+A^2+……A^x{if(x==1)return a;Node temp=sum(a,x>>1);if(x&1){Node tmp=power(a,(x>>1)+1);return add(add(mul(temp,tmp),temp),tmp);}else{Node tmp=power(a,(x>>1));return add(mul(tmp,temp),temp);}}int main(){ for(int i=0;i<n;i++) for(int j=0;j<n;j++) unit.mat[i][j]=(i==j); qiqi.mat[0][0]=1;qiqi.mat[0][1]=1;qiqi.mat[1][0]=1;qiqi.mat[1][1]=0;while(scanf("%d%d%d%d",&k,&b,&nn,&m)!=EOF){ Node res; res=power(qiqi,k);//A^k res=sum(res,nn-1);//A+A^2……+A^nn res=add(res,unit); Node ans=power(qiqi,b); res=mul(ans,res); printf("%I64d\n",res.mat[1][0]);}return 0;}

http://acm.hdu.edu.cn/showproblem.php?pid=3306

Another kind of Fibonacci

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 975 Accepted Submission(s): 387

Problem Description

Input

Output

Sample Input

Sample Output

Author

Source

Recommend

#include<cstdio>#include<iostream>#include<cstdlib>#include<stdio.h>#include<math.h>#define mm 10007using namespace std;const int MAX = 4;typedef struct{int m[MAX][MAX];} Matrix;Matrix P ={1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0};Matrix I ={1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1};Matrix matrixmul(Matrix a,Matrix b){int i,j,k;Matrix c;for (i = 0 ; i < MAX; i++)for (j = 0; j < MAX;j++){c.m[i][j] = 0;for (k = 0; k < MAX; k++)c.m[i][j] += (a.m[i][k] * b.m[k][j])%mm;c.m[i][j] =c.m[i][j]%mm;}return c;}Matrix quickpow(long long n){Matrix m = P, b = I;while (n >= 1){if (n & 1)b = matrixmul(b,m);n = n >> 1;m = matrixmul(m,m);}return b;}int main(){ int x,y,sum; int n; while(scanf("%d%d%d",&n,&x,&y)!=EOF) { x=x%mm;y=y%mm; int q=(x*x)%mm;int w=(y*y)%mm;int e=(2*x*y)%mm; P.m[1][1]=q;P.m[1][2]=w;P.m[1][3]=e; P.m[3][1]=x;P.m[3][3]=y; Matrix g=quickpow(n); int jk=(g.m[0][0]%mm+g.m[0][1]%mm+g.m[0][2]%mm+g.m[0][3]%mm)%mm; cout<<jk<<endl; }}
http://acm.hdu.edu.cn/showproblem.php?pid=3483Problem Description
InputOutputSample InputSample OutputSourceRecommend#include<iostream>#include<cstdlib>#include<stdio.h>#include<memory.h>#define ll __int64#define maxn 60using namespace std;ll x,mm,n;ll c[60][60];struct matrix{ ll m[maxn][maxn]; void init() { memset(m,0,sizeof(m)); }};matrix A,unit;matrix matrixmul(matrix a,matrix b){ matrix c; int i,j,k; for(i=0;i<=x+1;i++) for(j=0;j<=x+1;j++) { c.m[i][j]=0; for(k=0;k<=x+1;k++) c.m[i][j]+=a.m[i][k]*b.m[k][j]%mm; c.m[i][j]%=mm; } return c;}matrix quickpow(matrix p,ll nn){ matrix m=p,b=unit; while(nn) { if(nn&1) b=matrixmul(b,m); nn=nn>>1; m=matrixmul(m,m); } return b;}ll power(ll a,ll u){ ll res=1; while(u) { if(u&1) res=res*a%mm; u=u>>1; a=a*a%mm; } return res;}void init(){ for(int i=0;i<=x;i++) c[i][i]=c[i][0]=1; for(int i=0;i<=x;i++) for(int j=0;j<i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mm; for(int i=0;i<=x+1;i++) for(int j=0;j<=x+1;j++) { if(i==j) unit.m[i][j]=1; } A.m[0][0]=1; ll yy=0; for(int i=1;i<=x+1;i++) A.m[0][i]=c[x][yy++]*x%mm; ll xx=x; for(int i=1;i<=x;i++) { yy=0; for(int j=i;j<=x+1;j++) { A.m[i][j]=c[xx][yy]*x%mm; yy++; } xx--; } A.m[x+1][x+1]=x;}int main(){ //ll n; while(scanf("%I64d%I64d%I64d",&n,&x,&mm)!=EOF) { if(n<0&&x<0&&mm<0) break; if(n==1) { cout<<1%mm<<endl; continue; } A.init();unit.init(); init(); matrix g=quickpow(A,n-1); ll sum=0; sum=g.m[0][0]*x%mm; for(int i=1;i<=x+1;i++) sum=(sum+g.m[0][i]*x%mm)%mm; cout<<sum<<endl; }}
http://acm.hdu.edu.cn/showproblem.php?pid=3509也是构造矩阵，用到二项式，不赘述了。http://acm.hdu.edu.cn/showproblem.php?pid=2814这是一道斐波那契的好题，主要是寻找循环节，要找三次循环节。首先求G(1)的时候，由于对C取模，所以可以找到一个循环节。求G(n)的时候由于G(n)=G(n-1)^F(a^b),F(a^b)很大很大，所以必须利用降幂公式，a^b(mod c)即为a^(b mod phi(c)+phi(c))，b>=phi(c)，对F(a^b)进行降幂。这样求出G(n)后，由于G(n)是对C取模的，再求出G(n)这个序列的循环节。其中还要注意各种细节。