5.1 qbxt 一测 T2
求和
【问题描述】
组合数 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[],n,m;
int main()
{
freopen("sum.in","r",stdin);freopen("sum.out","w",stdout);
a[]=;a[]=;
for(int i=;i<=;i++)a[i]=(a[i-]*-a[i-]+*mod)%mod;
scanf("%d",&m);
while(m--)
{
scanf("%d",&n);
printf("%d\n",a[n]);
}
fclose(stdin);fclose(stdout);
}
最新文章
- interpreter(解释器模式)
- .NET程序员项目开发必知必会—Dev环境中的集成测试用例执行时上下文环境检查(实战)
- 使用Hive或Impala执行SQL语句,对存储在Elasticsearch中的数据操作
- 深入分析,理解jQuery.Deferred源码
- Mongoose简单学习笔记
- 仅使用处理单个数字的I/O例程,编写一个过程以输出任意实数(可以是负的)
- POJ - 2041Unreliable Message
- RFIDler - An open source Software Defined RFID Reader/Writer/Emulator
- AI-->;从新建文档开始说起,串联相关色彩知识
- sqlserver关于对列的权限控制
- Android WindowManager 监听返回键及home键
- Git Cmd
- mv 的使用
- jsDoc注释的规范
- P1417 烹调方案
- VisualStudio中的代码段
- ArcGIS for Silverlight 地图卷帘
- [hystar整理]Entity Framework 教程
- SQL server 2008 安装提示:属性不匹配
- LaTeX技巧561:LaTeX如何让每一章带有目录?
热门文章
- Educational Codeforces Round 21 D - Array Division (前缀和+二分)
- Android中R.java丢失不见的解决方案
- 黑客攻防技术宝典web实战篇:解析应用程序习题
- (五)SpringBoot如何定义全局异常
- Failed to convert property value of type &#39;java.util.LinkedHashMap&#39; to required type &#39;java.util.Map&#39; for property &#39;filters&#39;
- Wolfycz的娱乐赛题解
- 131 Palindrome Partitioning 分割回文串
- Invitation Cards POJ 1511 SPFA || dij + heap
- 05.NopCommerce给Topic表添加排序及类别字段
- js修改物理返回键功能