求和
【问题描述】
组合数 C(n,m)是从 n 个物品中取 m 个的方案数。
C(n,m)=(n!)/(m!(n-m)!)
斐波那契数列 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]
【输入格式】
一行一个数 T 表示数据组数
接下来 T 行每行一个数，表示 n
【输出格式】
输出 T 行，每行一个数表示答案，对 10^9+7 取模
【样例输入】
3
2
5
1000
【样例输出】
5
89
276439883
【数据规模和约定】
对于 30%的数据， n<=10
对于 60%的数据， n<=1000
对于 100%的数据， T<=1000，n<=10^6
考场解题：
这咋做啊计算一堆数的值，既然要用到阶乘和斐波那契数列，那
就可以先预处理出来，俩数组记录一下，然后咋做呢？苦思冥想二十
分种，我决定去上个厕所吧，观察观察忽然发现 C（n，0）和 C（n，
n）是相等的嘞，then 发现 C（n，k）和 C(n,n-k)貌似相等，看到这
感觉这题一定很神奇，研究研究吧，恩，把时间复杂度减半了，也算
是优化吧，可这对于 10^6 的数据该不过还是不过啊，不管了，先打
打 60 分吧，60 分也前两个样例对了，1000 咋也不过啊，这咋办，无
奈，打表找规律，2 5 13 34 89...
咦！！ a[k]=a[k-1]*3-a[k-2]诶，又试了几组手造样例，对啊，不过数
一 大 ， 一 % 就 会 出 事 ， 因 为 % 着 减 可 能 会 出 负 数 ， 根 据
a[k]=(a[k-1]*3-a[k-2]+2*mod)%mod,因为余数不可以是负数，根据
好像叫欧拉同余啥的吧。恩，写完以后，自我感觉良好。
期望的分：100
实际得分：100
正解：
对于%10 的数据，一个一个计算，只要不出太大错误，没问题。
60%得数据的话，预处理出来阶乘和斐波那切数列，枚举 1-n 进行
计算，完全不用担心回挂掉。
100%的话， 我比较幸运， 找了找规律， 发现a[i]=a[i-1]*3-a[i-2],
但是这好像不是正解诶， 老师说答案就是输入的 n 的在斐波那切数列
中的第 F（2*n）项。差不多吧，反正找对规律了。
代码：
#include<iostream> #include<cstring> #include<cstdio> #define mod 1000000007 using namespace std; long long a[1000011],n,m; int main() { freopen("sum.in","r",stdin);freopen("sum.out","w",stdout); a[0]=1;a[1]=2; for(int i=2;i<=1000001;i++)a[i]=(a[i-1]*3-a[i-2]+2*mod)%mod; scanf("%d",&m); while(m--) { scanf("%d",&n); printf("%d ",a[n]); } fclose(stdin);fclose(stdout); }