HDU1436: Neo 的区段求和

今天药忘吃喽~ 2022-05-28 03:47 137阅读 0赞

## 1436: Neo 的区段求和 ##

[http://acm.hpu.edu.cn/problem.php?id=1436][http_acm.hpu.edu.cn_problem.php_id_1436]

时间限制: 1 Sec 内存限制: 128 MB  
  
提交: 13 解决: 4 [统计][Link 1]

## 题目描述 ##

定义：

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 占一行。

## 样例输入 ##

0 1
    0 2

## 样例输出 ##

1
    3

## 提示 ##

注：

由同余定理可得如下结论：

(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][]

提交 [讨论][Link 2]

--------------------

<table style="border-spacing:0px;min-height:.01%;"> 
 <tbody> 
  <tr> 
   <td align="center" style="padding:0px;"><img src="http://acm.hpu.edu.cn/upload/image/20161007/20161007135905_40881.jpg" width="120" style="border:0px;vertical-align:middle;" alt=""></td> 
   <td align="center" style="padding:0px;"><a href="http://acm.hpu.edu.cn/setlang.php?lang=cn" style="background-color:transparent;color:rgb(51,122,183);" rel="nofollow">中文</a>&nbsp;&nbsp;<a href="http://acm.hpu.edu.cn/setlang.php?lang=en" style="background-color:transparent;color:rgb(51,122,183);" rel="nofollow">English</a>&nbsp;&nbsp;<a href="http://acm.hpu.edu.cn/settem.php?tem=new" style="background-color:transparent;color:rgb(51,122,183);" rel="nofollow">标准版</a>&nbsp;&nbsp;<a href="http://acm.hpu.edu.cn/settem.php?tem=lite" style="background-color:transparent;color:rgb(51,122,183);" rel="nofollow">精简版</a><br>Anything about HPU OnlineJudge, Please Contact Admin:<a href="mailto:BoilTask@qq.com" style="background-color:transparent;color:rgb(51,122,183);" rel="nofollow">BoilTask</a>&nbsp;<br>All Copyright Reserved 2010-2017&nbsp;<a href="http://acm.hpu.edu.cn/welcome/" style="background-color:transparent;color:rgb(51,122,183);" rel="nofollow">HPUACM</a><br>Based On&nbsp;<a href="http://acm.hpu.edu.cn/gpl-2.0.txt" style="background-color:transparent;color:rgb(51,122,183);" rel="nofollow">GPL2.0</a>&nbsp;<a href="https://github.com/zhblue/hustoj" style="background-color:transparent;color:rgb(51,122,183);" rel="nofollow">HUSTOJ Project</a>&nbsp;Modified by&nbsp;<a href="http://www.boiltask.com/" style="background-color:transparent;color:rgb(51,122,183);" rel="nofollow">BoilTask</a>&nbsp;<img src="http://c.cnzz.com/wapstat.php?siteid=1260840011&amp;r=http%3A%2F%2Facm.hpu.edu.cn%2Fproblemset.php&amp;rnd=836032111" width="0" height="0" style="border:0px;vertical-align:middle;" alt=""></td> 
  </tr> 
 </tbody> 
</table>

#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;
    }

[http_acm.hpu.edu.cn_problem.php_id_1436]: http://acm.hpu.edu.cn/problem.php?id=1436
[Link 1]: http://acm.hpu.edu.cn/problemstatus.php?id=1436
[LZ]: http://acm.hpu.edu.cn/problemset.php?search=LZ
[Link 2]: http://acm.hpu.edu.cn/bbs.php?pid=1436