Codeforces Round #FF C.DZY Loves Fibonacci Numbers

题目链接 题意 定义 $F_n$Fn​为斐波那契数列的第 $i$i项( $F_1=F_2=1$F1​=F2​=1) 给定长度为 $n$n的序列 $a$a，经行 $Q$Q次操作，两种操作类型： $(1,l,r)$(1,l,r)，对 $\forall i,l\le i\le r$∀i,l≤i≤r，令 $a_i$ai​加上 $F_{i-l+1}$Fi−l+1​ $(2,l,r)$(2,l,r)，求 ${\sum }_{i=l}^r{a}_i$∑i=lr​ai​ 答案 $mod10^9+9$mod109+9

题解 考虑斐波那契数列的通式 $F_n=\frac{1}{\sqrt{5}}\left[\right(\frac{1+\sqrt{5}}{2}{)}^n-\left(\frac{1-\sqrt{5}}{2}{)}^n\right]$Fn​=5 ​1​[(21+5 ​​)n−(21−5 ​​)n] 我们可以考虑是否可以通过预处理， $o\left(1\right)$o(1)的求出 $F_{n}mod10^9+9$Fn​mod109+9 我们可以暴力找到 $383008016^2\equiv 5(mod10^9+9)$3830080162≡5(mod109+9) $383008016\equiv \sqrt{5}(mod10^9+9)$383008016≡5 ​(mod109+9) 接着我们可以求出5和2的逆元，可以得到 $\frac{\sqrt{5}}{5}\equiv 2766001605(mod10^9+9)$55 ​​≡2766001605(mod109+9) $\frac{1+\sqrt{5}}{2}\equiv 691504013(mod10^9+9)$21+5 ​​≡691504013(mod109+9) $\frac{1-\sqrt{5}}{2}\equiv 308495997(mod10^9+9)$21−5 ​​≡308495997(mod109+9) 综上我们可以得到 $F_n\equiv 2766001605(691504013^n-308495997^n)mod10^9+9$Fn​≡2766001605(691504013n−308495997n)mod109+9 问题变为区间加等比数列，和区间求和。 接下来我们就考虑线段树如何实现区间加等比数列。我们只需要用一个 $x$x标记记录这段区间[L,R]加了几次 $q^1+q^2+q^3+...q^{R-l+1}$q1+q2+q3+...qR−l+1。比如说[1,8]加上 $q^1+q^2+..+q^8$q1+q2+..+q8，[1,8]节点的 $x=1$x=1标记下传左右儿子时，左儿子的 $x=1$x=1，右儿子是加上 $(q^1+q^2+q^3+q^4)\ast q^4$(q1+q2+q3+q4)∗q4，所以右儿子 $x=q^4$x=q4，接着用求和公式就很容易的可以求出区间和了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
#define MAX_V 10000
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const double PI=acos(-1);
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const ll mod=1e9+9;
const int maxn=3e5+5;
long long pow_mod(long long a,long long n,long long mod){
	long long ret = 1;
	long long temp = a%mod;
	while(n){
		if(n & 1)ret = ret*temp%mod; //mult_mod(ret,temp,mod);
		temp = temp*temp%mod; //mult_mod(temp,temp,mod);
		n >>= 1;
	}
	return ret;
}

const ll q1=691504013;
const ll q2=308495997;
ll bas = 276601605;

ll a[maxn],b[maxn];
ll val[maxn],sum[maxn];

struct node{
	int l,r;
	ll sum,ax,bx;
}s[maxn*4];

int n,m;
inline void PushUp(int p){
	s[p].sum=(s[p<<1].sum+s[p<<1|1].sum)%mod;
}
void build(int p,int l,int r){
	s[p].l=l;s[p].r=r;
	if(l==r){return;}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
void spread(int p){
	ll aa=s[p].ax,bb=s[p].bx;
	if(s[p].ax!=0||s[p].bx!=0){
		s[p<<1].ax=(s[p<<1].ax+aa)%mod;
		s[p<<1].bx=(s[p<<1].bx+bb)%mod;
		int len=s[p<<1].r-s[p<<1].l+1;
		s[p<<1|1].ax=(s[p<<1|1].ax+a[len]*aa%mod)%mod;
		s[p<<1|1].bx=(s[p<<1|1].bx+b[len]*bb%mod)%mod;
		int len2=s[p<<1|1].r-s[p<<1|1].l+1;
		s[p<<1].sum=(s[p << 1].sum + aa*(((a[len + 2] - a[2]) % mod + mod) % mod) % mod) % mod;
		s[p<<1].sum=(s[p << 1].sum - bb*(((b[len + 2] - b[2]) % mod + mod) % mod) % mod) % mod;
		s[p<<1|1].sum= (s[p << 1 | 1].sum + aa*a[len] % mod*(a[len2 + 2] - a[2] + mod) % mod) % mod;
		s[p<<1|1].sum=((s[p << 1 | 1].sum - bb*b[len] % mod*(b[len2 + 2] - b[2] + mod) % mod) % mod + mod) % mod;
		s[p].ax=s[p].bx=0;
	}
}
void change(int p,int l,int r,ll x,ll y){//区间修改 
	if(l==s[p].l&&s[p].r==r){
		s[p].ax=(s[p].ax+x)%mod;
		s[p].bx=(s[p].bx+y)%mod;
		int len=s[p].r-s[p].l+1;
		s[p].sum = (s[p].sum + x*(a[len + 2] - a[2] + mod) % mod + mod) % mod;
        s[p].sum = (s[p].sum - y*(b[len + 2] - b[2] + mod) % mod + mod) % mod;
		return;
	}
	spread(p);
	int mid=(s[p].l+s[p].r)>>1;
	if (r <= mid){
        change(p << 1, l, r, x, y);
    }
    else if (l > mid){
        change(p << 1 | 1, l, r, x, y);
    }
    else{
        int len = (mid - l + 1);
        change(p << 1, l, mid, x, y);
        change(p << 1 | 1, mid + 1, r, a[len] * x%mod, b[len] * y%mod);
    }
	PushUp(p);
}
ll ask(int p,int l,int r){//区间查询 
	if(s[p].l==l&&s[p].r==r)	return s[p].sum;
	spread(p);
	int mid=(s[p].l+s[p].r)>>1;
    if (r <= mid){
        return ask(p << 1, l, r);
    }
    else if (l > mid){
        return ask(p << 1 | 1, l, r);
    }
    else{
        return (ask(p << 1, l, mid) + ask(p << 1 | 1, mid + 1, r)) % mod;
    }
}
int main(){
    scanf("%d%d",&n,&m);
	a[0] = b[0] = 1;
    for (int i = 1; i <=n+5; i++){
        a[i] = a[i - 1] * q1%mod;
        b[i] = b[i - 1] * q2%mod;
    }
    val[0] = 0; sum[0] = 0;
    for (int i = 1; i <= n; i++){
        scanf("%lld", &val[i]);
        sum[i] = (sum[i - 1] + val[i]) % mod;
    }
    build(1, 1, n);
    int oper, l, r;
    for (int i = 0; i < m; i++){
        scanf("%d%d%d", &oper, &l, &r);
        if (oper == 1) change(1, l, r, 1, 1);
        else {
       // for(int i=1;i<=n;i++){
             ll res = ask(1, l, r);
            res = (res + mod) % mod;
            res = res*bas%mod;
            res = (res + ((sum[r] - sum[l - 1]) % mod+mod)%mod) % mod;
            printf("%lld\n", res);       		
			//} 

        }
    }
	return 0;
}