1436: Neo 的区段求和
http://acm.hpu.edu.cn/problem.php?id=1436
时间限制: 1 Sec 内存限制: 128 MB
提交: 13
解决: 4 统计
题目描述
定义：
F0=0F0=0
F1=1F1=1
F2=2F2=2
Fi=Fi−1+Fi−3,i>2Fi=Fi−1+Fi−3,i>2
S(l,r)=∑i=li≤rFiS(l,r)=∑i=li≤rFi
现在给定 l,rl,r，由于 s(l,r)s(l,r) 过大，你只要输出 s(l,r)%1000000007s(l,r)%1000000007
输入
多组输入数据，每组两个整数 l,rl,r。（0≤l≤r≤1060≤l≤r≤106）
输出
每组输出一个整数 s(l,r)%1000000007s(l,r)%1000000007
样例输入
样例输出
提示
注：
由同余定理可得如下结论：
(a∗b)%m=((a%m)∗(b%m))%m(a∗b)%m=((a%m)∗(b%m))%m
(a+b)%m=((a%m)+(b%m))%m(a+b)%m=((a%m)+(b%m))%m
来源
LZ
提交 讨论
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1000000007;
int f[(int)1e6+5];
int sum[(int)1e6+5];
void init() //打个表就好了
{
f[0]=0;
f[1]=1;
f[2]=2;
sum[0]=0;
sum[1]=sum[0]+f[1];
sum[2]=sum[1]+f[2];
for(int i=3;i<=1000000;i++)
{
f[i]=f[i-1]%mod+f[i-3]%mod;
sum[i]=sum[i-1]%mod+f[i]%mod;
sum[i]%=mod; //记得要让它也取下模
}
}
int main()
{
init();
int l,r;
while(scanf("%d %d",&l,&r)!=EOF)
printf("%d\n",(sum[r]-sum[l-1]+mod)%mod);//还是细节啊， sum[r]-sum[l-1]可能小于零，因此WA了一次
return 0;
}
