题目传送门

首先知道一个斐波那契数列的通式\(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_n\frac{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_n\frac{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\n",f[2*n]);
    }
    return 0;
}