#2719. 斐波那契

斐波那契

题目描述

DJL\red{DJL}为了避免成为一只咸鱼,来找czgj\red{czgj}学习Fibonacci\red{Fibonacci}数列。 通过czgj\red{czgj}的谆谆教导,DJL\red{DJL}明白了Fibonacci\red{Fibonacci}数列是这样定义的:

F(1)=1\red{F(1)=1};F(2)=1\red{F(2)=1};F(n)=F(n1)+F(n2)(n>2)\red{F(n)=F(n-1)+F(n-2)(n>2)}

Czgj\red{Czgj}深谙熟能生巧的道理,于是他给了DJL\red{DJL}一个数列,并安排了如下的训练计划:

1\red{1}、"1Lr\red{1 L r}",表示给ai\red{ai }加上F(iL+1)\red{F(i-L+1) ,}其中L<=i<=r\red{L<=i<=r }

2\red{2}、"2Lr\red{2 L r}",表示询问i=lrai modulo 1000000009(109+9)\red{\sum^{r}_{i=l}{a_i~modulo~1000000009(10^9+9)}}的值。

DJL\red{DJL}经过长时间的学习,感觉身体被掏空,他希望你能帮他解决这个问题。

输入格式

第一行两个整数n\red{n}m\red{m,}表示原始数列的长度,和总的训练次数。

第二行n\red{n}个整数a1,a2,...,an(1<=ai<=109)\red{a1,a2,...,an(1<=ai<=10^9) ,}表示czgj\red{czgj}DJL\red{DJL}的原始数列。

接下来m\red{m}行,每一行给出三个整数,表示问题描述中的两种训练的一种。

保证1<=L<=r<=n\red{1<=L<=r<=n }

输出格式

对于每一种形如"2Lr\red{2 L r}"的训练,输出一行一个整数值。

样例

输入样例

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]\red{a=[2,3,5,7] }

第二次询问,sum=2+3+5+7=17\red{sum=2+3+5+7=17 }

经过第三次操作,数列变为a=[2,4,6,9]\red{a=[2,4,6,9] }

第四次询问,sum=2+4+6=12\red{sum=2+4+6=12 }

数据范围

对于20%\red{20\%}的数据,1\red{1≤}n,m\red{n, m≤}100\red{100}

对于40%\red{40\%}的数据,1\red{1≤}n,m\red{n, m≤}1000\red{1000}

对于100%\red{100\%}的数据,1\red{1≤}n,m\red{n, m≤}100000\red{100000}

有关题目的提示

在阅读本段提示以前,请注意,以下给出的提示不一定是解题所必须的,也就是说,如果你跳过本段提示,也可以解决这个问题.解决问题也不一定要使用全部的提示。

特征方程:对于形如Fn=p\red{Fn=p}·Fn1+q\red{F_{n-1}+q}·Fn2\red{F_{n-2}}的递推数列,令x2=px+q\red{x^2=px+q,}若该方程有两个不同的实数根x1\red{x_1}x2\red{x_2,}F\red{F}的通项公式一定可以表示成F=a\red{F=a·}xn+B\red{xn+B}·xn\red{xn}的形式,将前两项F1\red{F_1}F2,\red{F_2,}代入即可得到α和β的值。

例如求解F1=5,F2=15,Fn=3Fn1+4Fn2\red{F_1=5,F_2=15,F_n=3F_{n-1}+4F_{n-2}}通项公式,令x2=3x+4\red{x^2=3x+4,}解得x1=4,x2=1\red{x_1=4,x_2=-1,}代入F1\red{F_1}F2\red{F_2,}解得α=1\red{α=1,}β=1\red{β=-1,}Fn=4n(1)n\red{F_n= 4^n-(-1)^n}

二次剩余:若gcd(a,m)=1\red{gcd(a,m) =1,}x2=\red{x^2=}a(modm)\red{a(mod m),}则称a\red{a}为模m\red{m }的二次剩余。

等比数列的前n\red{n}项和:对于等比数列an=a1\red{an=a1}·pn1\red{p^{n-1},}公式错误改 sn={n×a1    (p=1)(1pn)a11p  (p1)\red{s_n=\begin{cases}n\times a_1~~~~(p=1)\\\frac{(1-p^n)a_1}{1-p}~~(p≠1)\end{cases}}

Fibonacci\red{Fibonacci }数列的一个性质:若H1=a,H2=b,Hn=Hn2+Hn1\red{H_1=a,H_2=b,H_n=H_{n-2}+H_{n-1},}Hn=a\red{H_n=a}·Fn2+b\red{F_{n-2}+b}·Fn1\red{F_{n-1}}其中F\red{F}的定义见问题描述 。