51nod 1031+斐波那契和杨辉三角的一些基础知识

直接斐波那契。。。

#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 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行数字和为2^n-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+1)行中的每一项。

巴特西

51nod 1031+斐波那契和杨辉三角的一些基础知识

最新文章

热门文章