求和(团队题目)

题目传送门

首先知道一个斐波那契数列的通式(F_n = frac {1}{sqrt{5}} * ((frac{1+sqrt{5}}{2})^{n+1}-(frac{1-sqrt{5}}{2})^{n+1}))
二项式定理:((x+y)^n = Sigma_{i=0}^n C^i_nx^iy^{n-i})
原式S可转化为
(S = Sigma^n_{i=0}{C_n^i}*F_n)

=(Sigma^n_{i=0}{C_n^i}*frac {1}{sqrt{5}} * [(frac{1+sqrt{5}}{2})^{n+1}-(frac{1-sqrt{5}}{2})^{n+1}])

=(frac{1}{sqrt{5}}(Sigma^n_{i=0}{C_n^i}[(frac{1+sqrt{5}}{2})^{n+1}-(frac{1-sqrt{5}}{2})^{n+1})])

=(frac{1}{sqrt{5}}[(frac{1+sqrt{5}}{2})(frac{3+sqrt{5}}{2})^n)-(frac{1-sqrt{5}}{2})(frac{3-sqrt{5}}{2})^n])(由下文1式和2式推导而来)

=(frac{1}{sqrt{5}}[(frac{1+sqrt{5}}{2})^{2n+1}-(frac{1-sqrt{5}}{2})^{2n+1}]) (由下文3式和3式推导而来)

=(F_{2n})

1式:((frac{1+sqrt{5}}{2}+1)^n*(frac{1+sqrt{5}}{2})=Sigma_{i=0}^n C^i_nfrac{1+(sqrt{5}}{2})^i1^{n-i}=Sigma^n_{i=0}{C_n^i}(frac{1+sqrt{5}}{2})^{n+1})

2式:((frac{1-sqrt{5}}{2}+1)^n*(frac{1-sqrt{5}}{2})=Sigma_{i=0}^n C^i_nfrac{1-(sqrt{5}}{2})^i1^{n-i}=Sigma^n_{i=0}{C_n^i}(frac{1-sqrt{5}}{2})^{n+1}))

3式:((frac{1+sqrt{5}}{2})^2=(frac{3+sqrt{5}}{2}))

4式:((frac{1+sqrt{5}}{2})^2 = (frac{3+sqrt{5}}{2}))

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

int t,n,f[2000005],p = 1000000007;

int main() {
    scanf("%d",&t);
    f[1] = f[0] = 1;
    for(int i = 2;i <= 2000000; i++)
        f[i] = (f[i-2] + f[i-1]) % p;
    while(t--) {
        scanf("%d",&n);
        printf("%d
",f[2*n]);
    }
    return 0;
}