鲜花

因为陈煜轩太强了，没有写普通的代码。就让我这个蒟蒻来一篇吧。

思路

明显的发现，第一阶台阶有一种到达方法，第二阶台阶有两种到达方法。那么第三阶怎么到呢？就是第一阶的方法加上第二阶的方法。推出转移方程：

这样做就行了咩。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int f[100010];
main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	f[1]=1;
	f[2]=2;
	for(int i=3;i<=n;i++){
		f[i]=f[i-1]+f[i-2];
	}
	cout<<f[n];
	return 0;
}

打表或推式子可得答案为斐波那契数列。

题目让我用递归我就递归？我这么没面子的吗？

线性的斐波那契太低级了，我们来个高级的矩阵快速幂。

#include<bits/stdc++.h>
using namespace std;
int n=2;
long long m;
struct Matrix
{
    long long a[3][3];
    Matrix()
    {
        memset(a,0,sizeof(a));
    }
};
Matrix operator *(const Matrix &x,const Matrix &y)
{
	Matrix z;
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]);
	return z;
}
Matrix qpow(Matrix x,long long y)
{
    Matrix re=x;y--;
	for(;y>0;y>>=1)
	{
		if(y&1)re=re*x;
		x=x*x;
	}
	return re;
}
Matrix A,B,C;
int main()
{
    cin>>m;
    if(m<=1)
    {
        cout<<1<<endl;
        return 0;
    }
    A.a[1][1]=1;A.a[1][2]=1;
    A.a[2][1]=1;A.a[2][2]=0;
    B.a[1][1]=1;B.a[1][2]=1;
    C=B*qpow(A,m-1);
    cout<<C.a[1][1]<<endl;
    return 0;
}

打表或推式子可得答案为斐波那契数列。

题目让我用递归我就递归？我这么没面子的吗？

线性的斐波那契太高级了，我们来个低级的打表。

#include<bits/stdc++.h>
using namespace std;

long long a[65] {0,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961};
int main() {
	int n;
	cin>>n;
	cout<<a[n];
	return 0;
}