據(jù)出題的jzh老師所說...

求和
【問題描述】
組合數(shù) C(n,m)是從 n 個物品中取 m 個的方案數(shù)。
C(n,m)=(n!)/(m!(n-m)!)
斐波那契數(shù)列 F 滿足， F[0]=F[1]=1， n≥2 時 F[n]=F[n-1]+F[n-2]
給出 n，求 C(n,0)F[0]+C(n,1)F[1]+…+C(n,n)F[n]
【輸入格式】
一行一個數(shù) T 表示數(shù)據(jù)組數(shù)
接下來 T 行每行一個數(shù)，表示 n
【輸出格式】
輸出 T 行， 每行一個數(shù)表示答案，對 10^9+7 取模
【樣例輸入】
3 2 5
1000
【樣例輸出】
5
89
276439883
【數(shù)據(jù)規(guī)模和約定】
對于 30%的數(shù)據(jù)， n<=10
對于 60%的數(shù)據(jù)， n<=1000
對于 100%的數(shù)據(jù)， T<=1000， n<=10^6

?

【冷靜分析】

30%的點(diǎn)可以暴力過，由于斐波那契最為大家所熟知的是遞推式，但其實(shí)還有一個直接的通項(xiàng)公式；

然而本題是一個結(jié)論，可以通過以下證明：

?

轉(zhuǎn)載于:https://www.cnblogs.com/nopartyfoucaodong/p/8995664.html

總結(jié)

以上是生活随笔為你收集整理的一道清华期中考试题（逃）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。