kyu_115s 2011-10-01 00:48:00
点我顶贴
收藏
删除
过了两个点,说明不是预处理的问题呀,后面O(T)的输出超时了吗
状态: Unaccepted
测评机: Xeond[6]
得分: 20分
提交日期: 2011-10-1 15:43:00
有效耗时: 156毫秒
测试结果1: 通过本测试点|有效耗时93ms
测试结果2: 通过本测试点|有效耗时63ms
测试结果3: 选手程序运行超过时限
测试结果4: 选手程序运行超过时限
测试结果5: 选手程序运行超过时限
测试结果6: 选手程序运行超过时限
测试结果7: 选手程序运行超过时限
测试结果8: 选手程序运行超过时限
测试结果9: 选手程序运行超过时限
测试结果10:选手程序运行超过时限
代码:
#include<iostream>
#include<fstream>
#define fin cin
#include<stdio.h>
using namespace std;
unsigned int ans[1000002],add[1000002];
int main()
{
//fstream fin;fin.open("in.in",ios::in);
unsigned int t,i,j,k,cnt,n;
fin>>t;
add[1]=1,add[2]=1,add[3]=2;
ans[1]=2,ans[2]=3;
for(i=2;i<=500000;++i)
ans[i]=(ans[i-1]+add[i])%1000000009,add[i+1]=(add[i]+add[i-1])%1000000009;
for(i=0;i<t;++i)
{
fin>>n;
printf("%d\n",ans[n]);
}
//system("PAUSE");
return 0;
}