NEFU大一暑假集训-矩阵连乘

题集链接

OP

感谢老师的讲解与付出；

感谢ph和zsl两位大佬的指导与讨论；

夹带私货：
此节课的代表性内容和例题也已经整理到自己的贴子中：【笔记】数学

A Fibonacci Numbers

题目大意

对于大于8位的斐波那契数，输出其前四位及后四位；

思路

求前四位可以使用近似公式，求后四位可以使用矩阵快速幂对1e4取模；

使用近似公式求前四位时，由于幂次太高，会爆掉double和long double，我们可以先将其log10，再进行后续运算；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <algorithm>
#include <cstring>
#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
struct mtx{
	int a[2][2];
};
const int M = 10000;
const mtx sd={{{0,1},{1,1}}};
const double bas=log10((1+sqrt(5))/2);
const double fiv=log10(sqrt(5));
int f[1003],c;
mtx mul(mtx A,mtx B)
{
	mtx C;
	memset(C.a,0,sizeof(C.a));
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)
			{
				C.a[i][j]+=A.a[i][k]*B.a[k][j];
                C.a[i][j]%=M;
			}
	return C;
}
mtx mqm(mtx A,int b)
{
	mtx ans;
	memset(ans.a,0,sizeof(ans.a));
	for(int i=0;i<2;i++)ans.a[i][i]=1;
	for(;b;b>>=1)
	{
		if(b&1)ans=mul(ans,A);
		A=mul(A,A);
	}
	return ans;
}

int main()
{
    f[2]=f[1]=1;
    for(int i=3;i;i++)
    {
        f[i]=f[i-1]+f[i-2];
        if(f[i]>=1e8){c=i;break;}
    }
    //cout<<c;
    int n;
    while(~scanf("%d",&n))
    {
        if(n<c)printf("%d\n",f[n]);
        else
        {
            double frt=bas*n-fiv;
            frt=frt-floor(frt);
            printf("%d...%04d\n",(int)(1000*pow(10,frt)),mqm(sd,n).a[1][0]);
        }
    }
    return 0;
}

B How Many Fibs?

题目大意

对于给定a和b，求有多少斐波那契数在区间 [a,b] 中；

思路

由于数据量不大，我们可以先用高精度算出所有的斐波那契数，再遍历统计即可；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <algorithm>
#include <cstring>
#include <iostream>
#include <math.h>
#include <map>
using namespace std;
typedef long long ll;
string fbn[482],bod(102,'0'),g1,g2,l,r;
//map<string,int>mp;
int main()
{
    for(int i=0;i<=480;i++)fbn[i]=bod;
    fbn[0][101]=fbn[1][101]='1';
    //mp[fbn[0]]=0;
    for(int i=2;i<=480;i++)
    {
        int jin=0;
        for(int j=101;j>=0;j--)
        {
            int wei=fbn[i-1][j]-'0'+fbn[i-2][j]-'0'+jin;
            fbn[i][j]='0'+wei%10;
            jin=wei/10;
        }
        //mp[fbn[i]]=i;
    }
    //cout<<fbn[480];
    while(cin>>g1>>g2)
    {
        if(g1=="0"&&g2=="0")break;
        l.clear();
        r.clear();
        for(int i=1;i<=102-g1.length();i++)l+='0';
        for(int i=1;i<=102-g2.length();i++)r+='0';
        l+=g1;
        r+=g2;
        /* l[l.length()]=0;
        r[r.length()]=0; */
        //int nl=mp[lower_bound(fbn[0],fbn[481],l)],nr=mp[upper_bound(fbn[0],fbn[481],r)];
        //printf("%d\n",nr-nl);
        //cout<<l<<endl<<r<<endl;
        int ans=0;
        for(int i=1;i<=480;i++)
        {
            if(fbn[i]>=l&&fbn[i]<=r)ans++;//,cout<<fbn[i]<<endl;
        }
        printf("%d\n",ans);
    }
    return 0;
}
//0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

C Fibonacci Again

题目大意

定义了一个新的斐波那契数，求给定 f(i) 是否可以被3整除；

思路

找规律即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <algorithm>
#include <cstring>
#include <iostream>
#include <math.h>
#include <map>
using namespace std;
typedef long long ll;

int main()
{
    int n;
    while(cin>>n)
    {
        if(n%4==2)printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

D Hat’s Fibonacci

题目大意

定义了一个新的斐波那契数列，输出给定项的值；

思路

高精度即可；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <algorithm>
#include <cstring>
#include <iostream>
#include <math.h>
#include <map>
using namespace std;
typedef long long ll;
string fbn[7503],bod(2007,'0'),g1,g2,l,r;
//map<string,int>mp;
int main()
{
    for(int i=0;i<=7500;i++)fbn[i]=bod;
    fbn[1][2006]=fbn[2][2006]=fbn[3][2006]=fbn[4][2006]='1';
    //mp[fbn[0]]=0;
    for(int i=5;i<=7500;i++)
    {
        int jin=0;
        for(int j=2006;j>=0;j--)
        {
            int wei=fbn[i-1][j]-'0'+fbn[i-2][j]-'0'+fbn[i-3][j]-'0'+fbn[i-4][j]-'0'+jin;
            fbn[i][j]='0'+wei%10;
            jin=wei/10;
        }
    }
    int n,i;
    while (~scanf("%d",&n))
    {
        for(i=0;1;i++)if(fbn[n][i]!='0')break;
        for(i;i<=2006;i++)printf("%c",fbn[n][i]);
        printf("\n");
    }
    
    //cout<<fbn[7500];
    return 0;
}

E Fibonacci

题目大意

对于给定项的斐波那契数，输出其前四位；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <algorithm>
#include <cstring>
#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;

const int M = 10000;

const double bas=log10((1+sqrt(5))/2);
const double fiv=log10(sqrt(5));
int f[1003],c;

int main()
{
    f[2]=f[1]=1;
    for(int i=3;i;i++)
    {
        f[i]=f[i-1]+f[i-2];
        if(f[i]>=1e4){c=i;break;}
    }
    //cout<<c;
    int n;
    while(~scanf("%d",&n))
    {
        if(n<c)printf("%d\n",f[n]);
        else
        {
            double frt=bas*n-fiv;
            frt=frt-floor(frt);
            printf("%d\n",(int)(1000*pow(10,frt)));
        }
    }
    return 0;
}

F Another kind of Fibonacci

题目大意

给定 n ，输出∑i=0nf(i)2\sum_{i=0}^nf(i)^2 ；

代码

思路详见【笔记】数学中的例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <algorithm>
#include <cstring>
#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
struct mtx{
	int a[4][4];
};
const ll M = 10007;
mtx mul(mtx A,mtx B)
{
	mtx C;
	memset(C.a,0,sizeof(C.a));
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<4;k++)
			{
				C.a[i][j]+=A.a[i][k]*B.a[k][j];
                C.a[i][j]%=M;
			}
	return C;
}
mtx mqm(mtx A,int b)
{
	mtx ans;
	memset(ans.a,0,sizeof(ans.a));
	for(int i=0;i<2;i++)ans.a[i][i]=1;
	for(;b;b>>=1)
	{
		if(b&1)ans=mul(ans,A);
		A=mul(A,A);
	}
	return ans;
}

int main()
{
    ll n,x,y;
    while(~scanf("%lld%lld%lld",&n,&x,&y))
    {
        mtx bas={{{1,x*x%M,y*y%M,2*x*y%M},{0,x*x%M,y*y%M,2*x*y%M},{0,1,0,0},{0,x%M,0,y%M}}};
        bas=mqm(bas,n-1);
        printf("%lld\n",(2*bas.a[0][0]+bas.a[0][1]+bas.a[0][2]+bas.a[0][3])%M);
    }
    return 0;
}

G Fibonacci Subsequence

题目大意

给定一个数列，求其中符合斐波那契规律的（不要求连续）子数列的最长长度，并输出数列；

思路

dp，遍历所有的元素对作为前两项，在哈希表中判断是否存在第三项，并以此进行状态转移；

详见代码~

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

#define ll long long
#define N 3010
int a[N];
short dp[N][N]; 
int n;
map<int,int>mp;
map<int,int>::iterator it;
 
int main()
{ 
    int test=0;
    while(scanf("%d",&n)!=EOF)
    {
		if(test!=0) printf("\n");
		test++;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			dp[i][j]=1;
		mp.clear();
		int m=0,x,y;
		x=a[1];
		for(int i=n;i>=0;i--)
		{
			for(int j=1;j<=i-1;j++)
			{
				int k=a[i]+a[j];
				it=mp.find(k);
				if(it!=mp.end())
				{
					dp[j][i]=dp[i][it->second]+1;
					if(dp[j][i]>m)
					{
						m=dp[j][i];
						x=j; y=i;
					}
				}
	    	}
			mp[a[i]]=i;
		}
		if(n==1)
		{
			printf("1\n%d\n",a[1]);
			continue;
		}
		if(n==2)
		{
			printf("2\n%d %d\n",a[1],a[2]);
			continue;
		}
		if(m==0)
		{
			printf("2\n");
			printf("%d %d\n",a[1],a[2]); 
			continue;}
		printf("%d\n",m+1);
		x=a[x],y=a[y];
		printf("%d",x);
		for(int i=1;i<=m;i++)
		{
			printf(" %d",y);
			int z=x+y; x=y;y=z;
		}
		printf("\n");
    }
    return 0;
}

ED

矩阵连乘专题好像变成了斐波那契专题哈；

算法竞赛 > 比赛与题集
NEFU大一暑假集训-矩阵连乘
https://tanyuu.github.io/2021.07-12/NEFU大一暑假集训-矩阵连乘/
作者
F Juny
发布于
2021年8月12日
许可协议