您的位置: 首页  >  IT文章  >  矩阵链趁+斐波那契+快速幂 专题

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

分类: IT文章 • 2023-11-03 09:27:41
矩阵链乘+斐波那契+快速幂 专题

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
The Fibonacci sequence is the sequence of numbers such that every element is equal to the sum of the two previous elements, except for the first two elements f0 and f1 which are respectively zero and one.
矩阵链趁+斐波那契+快速幂 专题

What is the numerical value of the nth Fibonacci number?


 

Input
For each test case, a line will contain an integer i between 0 and 108 inclusively, for which you must compute the ith Fibonacci number fi. Fibonacci numbers get large pretty quickly, so whenever the answer has more than 8 digits, output only the first and last 4 digits of the answer, separating the two parts with an ellipsis (“...”).

There is no special way to denote the end of the of the input, simply stop when the standard input terminates (after the EOF).


 

Sample Input
0
1
2
3
4
5
35
36
37
38
39
40
64
65


 

Sample Output
0
1
1
2
3
5
9227465
14930352
24157817
39088169
63245986
1023...4155
1061...7723
1716...7565


 

Source
IPCP 2005 Northern Preliminary for Northeast North-America


 

Recommend
lcy

求斐波那契的前四位和后四位，后四位直接模上10000就行了，利用矩阵乘法

 

下面举例来说明计算前4 位
123456.32=1234.56*10^2
s=d.xxx*10^(len-4)
log10(s)=log10(d.xxxxx)+log10(10^(len-4))=log10(d.xxxx)+len-4;
log10(s)+4-len=log10(d.xxxx)
d.xxxx=10^(log10(s)+4-len)

s=(1/sqrt(5))*[(1+sqrt(5))/2.0]^i;
len=(int)log10(s)+1;
d.xxxx=10^(log10(s)+4-((int)log10(s)+1))=10^(log10(s)-(int)log10(s)+3);

#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 Description
Without expecting, Angel replied quickly.She says: "I'v heard that you'r a very clever boy. So if you wanna me be your GF, you should solve the problem called GF~. "
How good an opportunity that Gardon can not give up! The "Problem GF" told by Angel is actually "Gauss Fibonacci".
As we know ,Gauss is the famous mathematician who worked out the sum from 1 to 100 very quickly, and Fibonacci is the crazy man who invented some numbers.

Arithmetic progression:
g(i)=k*i+b;
We assume k and b are both non-nagetive integers.

Fibonacci Numbers:
f(0)=0
f(1)=1
f(n)=f(n-1)+f(n-2) (n>=2)

The Gauss Fibonacci problem is described as follows:
Given k,b,n ,calculate the sum of every f(g(i)) for 0<=i<n
The answer may be very large, so you should divide this answer by M and just output the remainder instead.


 

Input
The input contains serveral lines. For each line there are four non-nagetive integers: k,b,n,M
Each of them will not exceed 1,000,000,000.


 

Output
For each line input, out the value described above.


 

Sample Input
2 1 4 100
2 0 4 100


 

Sample Output
21
12


 

Author
DYGG


 

Source
HDU “Valentines Day” Open Programming Contest 2007-02-14


 

Recommend
linle

 

求f(ki+b)  0<=i<n

求斐波那契构造矩阵A[2][2]={1,1,1,0}   f(n)=A^n

所以根据题意有f(b)=A^b

                        f(k+b)=A^k+b

                        ……

                        f((n-1)k+b)=A^(n-1)k+b

s=f(b)+f(k+b)+f(2k+b)……+f((n-1)k+b)

s=A^b+A^k+b……A^(n-1)k+b

  =A^b(I+A^k+A^2k+……+A^(n-1)k)

把A^k看成一个整体，二分求解。

#include<iostream>
#include<stdio.h>
#define ll long long
using 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

As we all known , the Fibonacci series : F(0) = 1, F(1) = 1, F(N) = F(N - 1) + F(N - 2) (N >= 2).Now we define another kind of Fibonacci : A(0) = 1 , A(1) = 1 , A(N) = X * A(N - 1) + Y * A(N - 2) (N >= 2).And we want to Calculate S(N) , S(N) = A(0)2 +A(1)2+……+A(n)2.


Input

There are several test cases.
Each test case will contain three integers , N, X , Y .
N : 2<= N <= 231 – 1
X : 2<= X <= 231– 1
Y : 2<= Y <= 231 – 1


Output

For each test case , output the answer of S(n).If the answer is too big , divide it by 10007 and give me the reminder.


Sample Input

2 1 1 
3 2 3


Sample Output

6
196


Author

wyb


Source

HDOJ Monthly Contest – 2010.02.06


Recommend

wxl
关键是构建矩阵其实都so easy的。
构造矩阵P
Matrix P =
{
1,1,0,0,
0,x^2,y^2,2xy,
0,1,0,0,
0,x,0,y
};
Matrix Q=
{
s(n-1)
A(n-1)^2
A(n-2)^2
A(n-1)A(n-2)
};
Matrix W=
{
s(n)
A(n)^2
A(n-1)^2
A(n)A(n-1)
};
自然P*Q=W
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<math.h>
#define mm 10007
using 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=3483

A Very Simple Problem

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 510    Accepted Submission(s): 270


Problem Description
This is a very simple problem. Given three integers N, x, and M, your task is to calculate out the following value:

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


Input
There are several test cases. For each case, there is a line with three integers N, x, and M, where 1 ≤ N, M ≤ 2*109, and 1 ≤ x ≤ 50.
The input ends up with three negative numbers, which should not be processed as a case.

Output
For each test case, print a line with an integer indicating the result.

Sample Input
100 1 10000
3 4 1000
-1 -1 -1

Sample Output
5050
444

Source
2010 ACM-ICPC Multi-University Training Contest（5）——Host by BJTU

Recommend
zhengfeng
还是构造矩阵，用到二项式。
P=
{
    1,x*c(x,0),x*c(x,1)……x*c(x,x)
    0,x*c(x,0),x*c(x,1)……x*c(x,x)
    0,   0, x*c(x-1,1)……x*c(x-1,x-1)
    …………………………………………………………
    ……………………………………………………………………x
}
Q=
{
    Sn
    x^n*n^x
    x^n*n^(x-1)
    ……
    x^n*n^0
}
W=
{
    Sn+1
    x^(n+1)*(n+1)^x
    x^(n+1)*(n+1)^(x-1)
    ……
    x^(n+1)*(n+1)^0
}
P*Q=W
#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<memory.h>
#define ll __int64
#define maxn 60
using 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)这个序列的循环节。
其中还要注意各种细节。
 

相关推荐