CF446C DZY Loves Fibonacci Numbers

首先斐波那契数列有一个性质：

当\(f[1] = x,f[2] = y\)时，那么\(f[n] = x*f[n-1]+y*f[n-2]\)

还有一个性质：

任意两段不同的斐波那契数列逐项相加，所得数列仍然是个斐波那契数列。

所以对于这个题，维护一棵线段树，需要维护区间内斐波那契数列的第一项，第二项，区间和。

下传标记的时候，我们可以在做区间加前两项，在右区间可以求出总和再加上总和就行了。

时间复杂度为\(O(nlogn)\)

然而还有别的做法：

直接写出斐波那契数列的通项：
\[ f[n] = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n] \]
然后转化为线段树区间加等比数列，运用等比数列求和公式就可以。

同时值得注意的是，\(\sqrt{5}\)在\(\mod10^9+9\)意义下有二次剩余为383008016，so不用扩域。

代码为第一种做法。

#define B cout << "BreakPoint" << endl;
#define O(x) cout << #x << " " << x << endl;
#define O_(x) cout << #x << " " << x << " ";
#define Msz(x) cout << "Sizeof " << #x << " " << sizeof(x)/1024/1024 << " MB" << endl;
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#define LL long long
const int mod = 1e9 + 9;
const int N = 3e5 + 5;
using namespace std;
inline int read() {
    int s = 0,w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-')
            w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * w;
}
LL a[N],f[N],sum[N];
LL solve1(LL x,LL y,LL l){
    if(l == 1) return x;
    if(l == 2) return y;
    return (x * f[l - 2] + y * f[l - 1]) % mod;
}
LL solve2(LL x,LL y,LL l){
    if(l == 1) return x;
    if(l == 2) return (x + y) % mod;
    return (solve1(x,y,l + 2) - y + mod) % mod;
}
namespace Segment{
    #define ls k<<1
    #define rs k<<1|1
    struct node {
        LL c1,c2,sum;
    } t[N*20];
    void pushup(int k){
        t[k].sum = (t[ls].sum + t[rs].sum)%mod;
    }
    void pushdown(int k,int l,int r){
        if(!t[k].c1) return;
        int mid = l+r>>1;
        t[ls].c1 = (t[ls].c1 + t[k].c1) % mod;
        t[ls].c2 = (t[ls].c2 + t[k].c2) % mod;
        t[ls].sum = (t[ls].sum + solve2(t[k].c1,t[k].c2,mid - l + 1)) % mod;
        LL x = solve1(t[k].c1,t[k].c2,mid - l + 2),y = solve1(t[k].c1,t[k].c2,mid - l + 3);
        t[rs].c1 = (t[rs].c1 + x) % mod;
        t[rs].c2 = (t[rs].c2 + y) % mod;
        t[rs].sum = (t[rs].sum + solve2(x,y,r - mid)) % mod;
        t[k].c1 = 0,t[k].c2 = 0;
    }
    void update(int k,int l,int r,int L,int R){
        if(L <= l && r <= R){
            t[k].c1 = (t[k].c1 + f[l - L + 1]) % mod;
            t[k].c2 = (t[k].c2 + f[l - L + 2]) % mod;
            t[k].sum = (t[k].sum + solve2(f[l - L + 1],f[l - L + 2],r - l + 1)) % mod;
            return ;
        }
        pushdown(k,l,r);
        int mid = l+r>>1;
        if(L <= mid) update(ls,l,mid,L,R);
        if(R > mid) update(rs,mid + 1,r,L,R);
        pushup(k);
    }
    LL query(int k,int l,int r,int L,int R){
        LL res = 0;
        if(L <= l && r <= R){
            res = t[k].sum;
            return (res+mod)%mod;
        }
        pushdown(k,l,r);
        int mid = l+r>>1;
        if(L <= mid) res += query(ls,l,mid,L,R);
        if(R > mid) res += query(rs,mid + 1,r,L,R);
        return (res+mod) % mod;
    }
}
int n,m;
void init(){
    n = read(),m = read();
    for(int i = 1;i <= n;i++){
        LL x = read();
        a[i] = (a[i - 1] + x) % mod;
    }
    f[1] = 1,f[2] = 1;
    for(int i = 3;i <= n + 2;i++) f[i] = (f[i - 1] + f[i - 2]) % mod;
    return ;
}
using namespace Segment;
void solve(){
    for(int i = 1; i <= m; i++) {
        int opt = read(),x = read(),y = read();
        if (opt == 1) update(1, 1, n, x, y);
        else printf("%lld\n", (mod + query(1,1,n,x,y) + a[y] - a[x - 1]) % mod);
    }
    return ;
}
int main(){
    init();
    solve();
    return 0;
}

CF446C DZY Loves Fibonacci Numbers

原文：https://www.cnblogs.com/excellent-zzy/p/12404349.html