直接斐波那契。。。
#include<stdio.h>
#include<queue>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const LL mod=1e9+7; LL a[1010];
int main()
{
a[1]=1;
a[2]=2;
for(int i=3;i<=1000;i++)
a[i]=(a[i-1]+a[i-2])%mod;
LL n;
scanf("%lld",&n);
printf("%lld\n",a[n]);
return 0;
}
斐波那契和杨辉三角上的组合数知识
斐波那契数列并不陌生,F(N)=F(N-1)+F(N-2);
f⑴=C(0,0)=1。
f⑵=C(1,0)=1。
f⑶=C(2,0)+C(1,1)=1+1=2。
f⑷=C(3,0)+C(2,1)=1+2=3。
f⑸=C(4,0)+C(3,1)+C(2,2)=1+3+1=5。
f⑹=C(5,0)+C(4,1)+C(3,2)=1+4+3=8。
F⑺=C(6,0)+C(5,1)+C(4,2)+C(3,3)=1+5+6+1=13。
……
F(n)=C(n-1,0)+C(n-2,1)+…+C(n-1-m,m)(m<=n-1-m)【重要】!
上面的图形非常像杨辉三角,但是还差一点;
杨辉三角:
1
1 1
1 2 1
1 3
3 1
1
4 6
4 1
1 5 10
10 5
1
1 6 15
20 16 6 1
给出几个重要的性质
1. 每个数等于它上方两数之和。
2. 第n行数字和为2n-1。
3. 第n行的m个数可表示为 C(n-1,m-1),即为从n-1个不同元素中取m-1个元素的组合数。
4. 每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和,这也是组合数的性质之一。即 C(n+1,i)=C(n,i)+C(n,i-1)。
5. (a+b)n的展开式中的各项系数
依次对应杨辉三角的第(n+1)行中的每一项。