【题解】csp.ac #61. 乘积求和(T2-20)

题目

csp.ac #61. 乘积求和(T2-20)

思路

求 (sum_{i=0}^{n} C_{n}^{i} imes F_i)，其中 (C_n^i) 为组合数，(F_i) 为斐波那契数列。

(egin{aligned} sum_{i=0}^{n} C_{n}^{i} imes F_i &= sum_{i=0}^{n}C_{n}^{i}frac{1}{sqrt{5}}[(frac{1+sqrt{5}}{2})^i-(frac{1-sqrt{5}}{2})^i] ext{（斐波那契通项公式）}\\ &=frac{1}{sqrt{5}}sum_{i=0}^{n}C_n^i[(frac{1+sqrt{5}}{2})^i-(frac{1-sqrt{5}}{2})^i] ext{（提出一个常数）} \\ &=frac{1}{sqrt{5}}sum_{i=0}^{n}C_n^i(frac{1+sqrt{5}}{2})^i-frac{1}{sqrt{5}}sum_{i=0}^{n}C_n^i(frac{1-sqrt{5}}{2})^i \\ &=frac{1}{sqrt{5}}[(1+frac{1+sqrt{5}}{2})^n- (1+frac{1-sqrt{5}}{2})^n] ext{（二项式定理）}\\ &=frac{1}{sqrt{5}}[(frac{3+sqrt{5}}{2})^n- (frac{3-sqrt{5}}{2})^n] \\ &=frac{1}{sqrt{5}}[[(frac{1+sqrt{5}}{2})^2]^n- (frac{1-sqrt{5}}{2})^2]^n] \\ &=frac{1}{sqrt{5}}[(frac{1+sqrt{5}}{2})^{2n}- (frac{1-sqrt{5}}{2})^{2n}] \\ &=F_{2n} ext{（斐波那契通项公式）}end{aligned})

二项式定理，不会的可以康康
((1+b)^n = sumlimits_{i=0}^{n}C_{n}^{i}b^i)

Code

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>

inline void read(int &T) {
	int x=0;bool f=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	T=f?-x:x;
}

const int mod=1e9+7;
int t,n,f[2000001];

int main() {
	read(t);f[1]=f[0]=1;
	for(int i=2;i<=2000000;++i) {
		f[i]=(f[i-1]+f[i-2])%mod;
	}
	while(t--) {
		read(n);
		std::cout<<f[2*n]<<'
';;
	}
	return 0;
}