题目描述
DJL为了避免成为一只咸鱼,来找czgj学习Fibonacci数列。
通过czgj的谆谆教导,DJL明白了Fibonacci数列是这样定义的:
F(1)=1;F(2)=1;F(n)=F(n−1)+F(n−2)(n>2)
Czgj深谙熟能生巧的道理,于是他给了DJL一个数列,并安排了如下的训练计划:
1、"1Lr",表示给ai加上F(i−L+1),其中L<=i<=r;
2、"2Lr",表示询问∑i=lrai modulo 1000000009(109+9)的值。
DJL经过长时间的学习,感觉身体被掏空,他希望你能帮他解决这个问题。
输入格式
第一行两个整数n和m,表示原始数列的长度,和总的训练次数。
第二行n个整数a1,a2,...,an(1<=ai<=109),表示czgj给DJL的原始数列。
接下来m行,每一行给出三个整数,表示问题描述中的两种训练的一种。
保证1<=L<=r<=n。
输出格式
对于每一种形如"2Lr"的训练,输出一行一个整数值。
样例
输入样例
4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3
输出样例
17
12
提示
样例解释
经过第一次操作,数列变为a=[2,3,5,7];
第二次询问,sum=2+3+5+7=17;
经过第三次操作,数列变为a=[2,4,6,9];
第四次询问,sum=2+4+6=12。
数据范围
对于20%的数据,1≤n,m≤100;
对于40%的数据,1≤n,m≤1000;
对于100%的数据,1≤n,m≤100000。
有关题目的提示
在阅读本段提示以前,请注意,以下给出的提示不一定是解题所必须的,也就是说,如果你跳过本段提示,也可以解决这个问题.解决问题也不一定要使用全部的提示。
特征方程:对于形如Fn=p·Fn−1+q·Fn−2的递推数列,令x2=px+q,若该方程有两个不同的实数根x1和x2,则F的通项公式一定可以表示成F=a⋅xn+B·xn的形式,将前两项F1和F2,代入即可得到α和β的值。
例如求解F1=5,F2=15,Fn=3Fn−1+4Fn−2通项公式,令x2=3x+4,解得x1=4,x2=−1,代入F1和F2,解得α=1,β=−1,则Fn=4n−(−1)n。
二次剩余:若gcd(a,m)=1,且x2=a(modm),则称a为模m的二次剩余。
等比数列的前n项和:对于等比数列an=a1·pn−1,公式错误改 sn={n×a1 (p=1)1−p(1−pn)a1 (p=1)
Fibonacci数列的一个性质:若H1=a,H2=b,Hn=Hn−2+Hn−1,则Hn=a·Fn−2+b·Fn−1其中F的定义见问题描述 。