Codeforces 446C - DZY Loves Fibonacci Numbers（斐波那契数列 线段树）
你可能会疑惑我为什么要写 *2400 的题的题解
首先一个很明显的想法是，看到斐波那契数列和 \(10^9 9\) 就想到通项公式，\(F_i=\dfrac{1}{\sqrt{5}}((\dfrac{1 \sqrt{5}}{2})^n-(\dfrac{1-\sqrt{5}}{2})^n)\)。并且 \(5\) 在模 \(10^9 9\) 意义下的二次剩余存在，为 \(383008016\)。
我们建两棵线段树分别维护展开式中 \((\dfrac{1 \sqrt{5}}{2})^n\) 和 \((\dfrac{1-\sqrt{5}}{2})^n\) 的部分，查询的时候原本的 \(a_i\) 可以做个前缀和 \(\mathcal O(1)\) 加上，其余部分直接在两棵线段树上区间查询相减并乘个 \(\dfrac{1}{\sqrt{5}}\) 即可。区间加操作相当于在两棵线段树区间 \([l,r]\) 加等比数列，这个可以用线段树区间加等比数列的套路维护。具体来说，我们以 \((\dfrac{1 \sqrt{5}}{2})^n\) 为例，线段树每个区间 \([L,R]\) 的懒标记 \(lz\) 表示该区间中第 \(i\in [L,R]\) 项的值要增加 \((\dfrac{1 \sqrt{5}}{2})^{i-L}\)，然后你预处理 \(s_i=\sum\limits_{j=0}^{i-1}(\dfrac{1 \sqrt{5}}{2})^j\) 就可以 \(\mathcal O(1)\) 下放懒标记了。时间复杂度线对。
#include <bits/stdc .h>using namespace std;#define fi first#define se second#define fill0(a) memset(a,0,sizeof(a))#define fill1(a) memset(a,-1,sizeof(a))#define fillbig(a) memset(a,63,sizeof(a))#define pb push_back#define ppb pop_back#define mp make_pairtemplate<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}typedef pair<int,int> pii;typedef long long ll;typedef unsigned int u32;typedef unsigned long long u64;namespace fastio{#define FILE_SIZE 1<<23char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;inline char getc(){return p1==p2&&(p2=(p1=rbuf) fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1 ;}inline void putc(char x){(*p3 =x);}template<typename T> void read(T &x){x=0;char c=getchar();T neg=0;while(!isdigit(c)) neg|=!(c^'-'),c=getchar();while(isdigit(c)) x=(x<<3) (x<<1) (c^48),c=getchar();if(neg) x=(~x) 1;}template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x^48);}template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x 1;recursive_print(x);}void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}}const int SQRT_5=383008016;const int INV2=5e8 5;const int MAXN=3e5;const int MOD=1e9 9;int qpow(int x,int e){int ret=1;for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;return ret;}int n,qu,INV_SQRT_5,a[MAXN 5],ss[MAXN 5];struct segtree{int base,pw[MAXN 5],sum[MAXN 5];void prework(){pw[0]=sum[0]=1;for(int i=1;i<=n;i ) pw[i]=1ll*pw[i-1]*base%MOD;for(int i=1;i<=n;i ) sum[i]=(sum[i-1] pw[i])%MOD;}struct node{int l,r,sum,lz;} s[MAXN*4 5];void build(int k,int l,int r){s[k].l=l;s[k].r=r;if(l==r) return;int mid=l r>>1;build(k<<1,l,mid);build(k<<1|1,mid 1,r);}void pushup(int k){s[k].sum=(s[k<<1].sum s[k<<1|1].sum)%MOD;}void pushdown(int k){if(s[k].lz){s[k<<1].lz=(s[k<<1].lz s[k].lz)%MOD;s[k<<1].sum=(s[k<<1].sum 1ll*s[k].lz*sum[s[k<<1].r-s[k<<1].l])%MOD;s[k<<1|1].lz=(s[k<<1|1].lz 1ll*s[k].lz*pw[s[k<<1].r-s[k<<1].l 1])%MOD;s[k<<1|1].sum=(s[k<<1|1].sum 1ll*s[k].lz*sum[s[k<<1|1].r-s[k<<1|1].l]%MOD*pw[s[k<<1].r-s[k<<1].l 1])%MOD;s[k].lz=0;}}void modify(int k,int l,int r,int x){if(l<=s[k].l&&s[k].r<=r){s[k].sum=(s[k].sum 1ll*x*sum[s[k].r-s[k].l])%MOD;s[k].lz=(s[k].lz x)%MOD;return;} pushdown(k);int mid=s[k].l s[k].r>>1;if(r<=mid) modify(k<<1,l,r,x);else if(l>mid) modify(k<<1|1,l,r,x);else modify(k<<1,l,mid,x),modify(k<<1|1,mid 1,r,1ll*x*pw[mid-l 1]%MOD);pushup(k);}int query(int k,int l,int r){if(l<=s[k].l&&s[k].r<=r) return s[k].sum;pushdown(k);int mid=s[k].l s[k].r>>1;if(r<=mid) return query(k<<1,l,r);else if(l>mid) return query(k<<1|1,l,r);else return (query(k<<1,l,mid) query(k<<1|1,mid 1,r))%MOD;}} s1,s2;int main(){INV_SQRT_5=qpow(SQRT_5,MOD-2);scanf("%d%d",&n,&qu);for(int i=1;i<=n;i ) scanf("%d",&a[i]),ss[i]=(ss[i-1] a[i])%MOD;s1.base=1ll*(SQRT_5 1)*INV2%MOD;s2.base=1ll*(1-SQRT_5 MOD)*INV2%MOD;s1.prework();s2.prework();s1.build(1,1,n);s2.build(1,1,n);while(qu--){int opt,l,r;scanf("%d%d%d",&opt,&l,&r);if(opt==1) s1.modify(1,l,r,s1.base),s2.modify(1,l,r,s2.base);else printf("%d\n",((ss[r]-ss[l-1] MOD)%MOD 1ll*(s1.query(1,l,r)-s2.query(1,l,r) MOD)*INV_SQRT_5%MOD)%MOD);}return 0;}/*4 41 2 3 41 1 42 1 42 1 22 3 4*/当然我之所以写这个题解是因为还有别的做法。
上面的做法用到了模数是 \(10^9 9\) 的性质，倘若模数不是 \(10^9 9\) 那岂不就歇菜了？
考虑斐波那契数列的一个性质 \(F_n=F_{n-m}F_{m-1} F_{n-m 1}F_m\)。
那么我们就有 \(F_{i-l 1}=F_iF_{-l} F_{i 1}F_{-l 1}\)
这里我们定义负数下标的斐波那契数列为：\(F_{-1}=F_1-F_0=1,F_{-2}=F_0-F_{-1}=-1,F_{-3}=F_{-1}-F_{-2}=2\)，以此类推。
显然 \(F_{-i}=(-1)^{i 1}F_i\)
至于为什么等式 \(F_n=F_{n-m}F_{m-1} F_{n-m 1}F_m\) 对负数下标的斐波那契数列同样适用，可用跷跷板归纳法证明，这里就不再赘述了。
知道这个性质之后，考虑将代求的数列拆成两部分，\(a_i=F_ib_i F_{i 1}c_i\)。那么一次区间修改操作相当于令 \([l,r]\) 中的 \(b_i\) 加上 \(F_{-l}\)，\(c_i\) 加上 \(F_{-l 1}\)。于是问题转化为对于数列 \(A_i=B_iC_i\) 进行两种操作，将区间 \([l,r]\) 中的 \(C_i\) 加上 \(v\)，求区间 \([l,r]\) 中所有 \(A_i\) 的和。这个可以用线段树维护，线段树上区间 \([L,R]\) 的懒标记 \(lz\) 表示 \([L,R]\) 中的 \(C_i\) 要加上 \(lz\)。考虑线段树每个区间记录一个 \(sum\) 表示 \(\sum\limits_{i=L}^RB_i\)，这样可做到 \(\mathcal O(1)\) 下放懒标记，时间复杂度还是线对。
btw P5138 也是用的这个套路，既然这题写了题解那题就不写了罢
#include <bits/stdc .h>using namespace std;#define fi first#define se second#define fill0(a) memset(a,0,sizeof(a))#define fill1(a) memset(a,-1,sizeof(a))#define fillbig(a) memset(a,63,sizeof(a))#define pb push_back#define ppb pop_back#define mp make_pairtemplate<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}typedef pair<int,int> pii;typedef long long ll;typedef unsigned int u32;typedef unsigned long long u64;namespace fastio{#define FILE_SIZE 1<<23char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;inline char getc(){return p1==p2&&(p2=(p1=rbuf) fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1 ;}inline void putc(char x){(*p3 =x);}template<typename T> void read(T &x){x=0;char c=getchar();T neg=0;while(!isdigit(c)) neg|=!(c^'-'),c=getchar();while(isdigit(c)) x=(x<<3) (x<<1) (c^48),c=getchar();if(neg) x=(~x) 1;}template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x^48);}template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x 1;recursive_print(x);}void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}}const int MAXN=3e5;const int MOD=1e9 9;int n,qu,a[MAXN 5],fib[MAXN 5],fib_neg[MAXN 5],sum[MAXN 5];struct node{int l,r,sum1,sum2,val1,val2,lz1,lz2;} s[MAXN*4 5];void pushup(int k){s[k].val1=(s[k<<1].val1 s[k<<1|1].val1)%MOD;s[k].val2=(s[k<<1].val2 s[k<<1|1].val2)%MOD;}void pushdown(int k){if(s[k].lz1||s[k].lz2){s[k<<1].val1=(s[k<<1].val1 1ll*s[k<<1].sum1*s[k].lz1)%MOD;s[k<<1].val2=(s[k<<1].val2 1ll*s[k<<1].sum2*s[k].lz2)%MOD;s[k<<1].lz1=(s[k<<1].lz1 s[k].lz1)%MOD;s[k<<1].lz2=(s[k<<1].lz2 s[k].lz2)%MOD;s[k<<1|1].val1=(s[k<<1|1].val1 1ll*s[k<<1|1].sum1*s[k].lz1)%MOD;s[k<<1|1].val2=(s[k<<1|1].val2 1ll*s[k<<1|1].sum2*s[k].lz2)%MOD;s[k<<1|1].lz1=(s[k<<1|1].lz1 s[k].lz1)%MOD;s[k<<1|1].lz2=(s[k<<1|1].lz2 s[k].lz2)%MOD;s[k].lz1=s[k].lz2=0;}}void build(int k,int l,int r){s[k].l=l;s[k].r=r;if(l==r){s[k].sum1=fib[l];s[k].sum2=fib[l 1];return;}int mid=l r>>1;build(k<<1,l,mid);build(k<<1|1,mid 1,r);s[k].sum1=(s[k<<1].sum1 s[k<<1|1].sum1)%MOD;s[k].sum2=(s[k<<1].sum2 s[k<<1|1].sum2)%MOD;}void modify(int k,int l,int r,int v1,int v2){if(l<=s[k].l&&s[k].r<=r){s[k].lz1=(s[k].lz1 v1)%MOD;s[k].lz2=(s[k].lz2 v2)%MOD;s[k].val1=(s[k].val1 1ll*s[k].sum1*v1%MOD)%MOD;s[k].val2=(s[k].val2 1ll*s[k].sum2*v2%MOD)%MOD;return;} pushdown(k);int mid=s[k].l s[k].r>>1;if(r<=mid) modify(k<<1,l,r,v1,v2);else if(l>mid) modify(k<<1|1,l,r,v1,v2);else modify(k<<1,l,mid,v1,v2),modify(k<<1|1,mid 1,r,v1,v2);pushup(k);}int query(int k,int l,int r){if(l<=s[k].l&&s[k].r<=r) return (s[k].val1 s[k].val2)%MOD;pushdown(k);int mid=s[k].l s[k].r>>1;if(r<=mid) return query(k<<1,l,r);else if(l>mid) return query(k<<1|1,l,r);else return (query(k<<1,l,mid) query(k<<1|1,mid 1,r))%MOD;}int main(){scanf("%d%d",&n,&qu);for(int i=1;i<=n;i ) scanf("%d",&a[i]),sum[i]=(sum[i-1] a[i])%MOD;fib[1]=fib[2]=1;fib_neg[1]=1;fib_neg[2]=MOD-1;for(int i=3;i<=n 1;i ){fib[i]=(fib[i-1] fib[i-2])%MOD;if(~i&1) fib_neg[i]=MOD-fib[i];else fib_neg[i]=fib[i];} build(1,1,n);while(qu--){int opt,l,r;scanf("%d%d%d",&opt,&l,&r);if(opt==1) modify(1,l,r,fib_neg[l],fib_neg[l-1]);else printf("%d\n",((sum[r]-sum[l-1] MOD)%MOD query(1,l,r))%MOD);}return 0;}当然此题还有可能有别的方法，不过由于我太懒了就不写了/wq
赞 (0)