题解 CF718C 【Sasha and Array】

怎么全是矩阵啊emmm来个不一样的做法 首先我们有结论$f_{n+m}=f_nf_{m-1}+f_{n+1}f_m=f_nf_{m+1}+f_{n+1}f_m-f_nf_m$ 证明可以通过展开$f_n$得到: $\begin{aligned}f_n&=f_2f_{n-1}+f_1f_{n-2}\\&=f_3f_{n-2}+f_2f_{n-3}\\&=f_4f_{n-3}+f_3f_{n-4}\\&\cdots\\&=f_{m+1}f_{n-m}+f_{m}f_{n-m-1}\end{aligned}$ 类似地有$f_{n+1+m}=f_nf_m+f_{n+1}f_{m+1}$ 于是我们只要维护区间$f_n$的和以及$f_{n+1}$的和就好了.对于标记，我们也维护$f_m$和$f_{m+1}$，然后和区间和一样修改 剩下的问题就是快速计算$f_n$的值了.题解都是矩阵快速幂，然而我们有更快的做法 众所周知$f_n=\frac{1}{\sqrt{5}}\left((\tfrac{1+\sqrt{5}}{2})^n-(\tfrac{1-\sqrt{5}}{2})^n\right)$，我们可以考虑直接按照这个式子计算.然而$\sqrt{5}$在模$1e9+7$下不存在，所以我们手写一个$a+b\sqrt{5}$类型，重载加减乘法运算 另一点是快速幂还有$log$的复杂度比较烦，我们使用光速幂，具体地，有 $a^b=a^{32768x+y}=(a^{32768})^xa^y$，预处理$a$和$a^{32768}$的$0$到$32767$次幂即可$O(1)$求幂. 然后就以吊打当前rank2 10s的速度A掉了这道题233 ```cpp #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int LIM=32768,inv2=500000004,inv5=400000003,mod=1e9+7,N=2e6; struct comp { int a,b; comp operator +(const comp &t)const{return (comp){(a+t.a)%mod,(b+t.b)%mod};} comp operator -(const comp &t)const{return (comp){(a-t.a)%mod,(b-t.b)%mod};} comp operator *(const comp &t)const{return (comp){(1ll*a*t.a+5ll*b*t.b)%mod,(1ll*a*t.b+1ll*b*t.a)%mod};} }pw0[2][LIM+100],pw1[2][LIM+100]; const comp F0={inv2,inv2},F1={inv2,mod-inv2}; struct Node { int s1,s2; Node operator +(const Node &a)const{return (Node){(s1+a.s1)%mod,(s2+a.s2)%mod};} Node operator *(const Node &a)const{return (Node){(1ll*s1*a.s2+1ll*(s2-s1)*a.s1)%mod,(1ll*s1*a.s1+1ll*s2*a.s2)%mod};} }a[N],tag[N]; int w[N],n,m; void make() { pw0[0][0]=pw1[0][0]=pw0[1][0]=pw1[1][0]=(comp){1,0}; for(int i=1;i<=LIM;i++)pw0[0][i]=pw0[0][i-1]*F0,pw0[1][i]=pw0[1][i-1]*F1; comp t0=pw0[0][LIM],t1=pw0[1][LIM]; for(int i=1;i<=LIM;i++)pw1[0][i]=pw1[0][i-1]*t0,pw1[1][i]=pw1[1][i-1]*t1; } comp qpower(int n,int f){return pw1[f][(n>>15)&32767]*pw0[f][n&32767];} int F(int n){return ((comp){0,inv5}*(qpower(n,0)-qpower(n,1))).a;} void build(int rot,int lt,int rt) { tag[rot]=(Node){0,1}; if(lt==rt){a[rot]=(Node){F(w[lt]),F(w[lt]+1)};return;} int mid=(lt+rt)>>1; build(rot<<1,lt,mid),build(rot<<1|1,mid+1,rt); a[rot]=a[rot<<1]+a[rot<<1|1]; } void upd(int rot,Node x){a[rot]=a[rot]*x,tag[rot]=tag[rot]*x;} void pushdown(int rot) { if(tag[rot].s1!=0||tag[rot].s2!=1) { Node t=tag[rot];tag[rot]=(Node){0,1}; upd(rot<<1,t),upd(rot<<1|1,t); } } void update(int rot,int lt,int rt,int lq,int rq,Node x) { if(lt>=lq&&rt<=rq){upd(rot,x);return;} int mid=(lt+rt)>>1;pushdown(rot); if(lq<=mid)update(rot<<1,lt,mid,lq,rq,x); if(rq>mid)update(rot<<1|1,mid+1,rt,lq,rq,x); a[rot]=a[rot<<1]+a[rot<<1|1]; } int query(int rot,int lt,int rt,int lq,int rq) { if(lt>=lq&&rt<=rq)return a[rot].s1; int mid=(lt+rt)>>1;pushdown(rot); if(rq<=mid)return query(rot<<1,lt,mid,lq,rq); else if(lq>mid)return query(rot<<1|1,mid+1,rt,lq,rq); else return (query(rot<<1,lt,mid,lq,mid)+query(rot<<1|1,mid+1,rt,mid+1,rq))%mod; } int main() { scanf("%d%d",&n,&m);make(); for(int i=1;i<=n;i++)scanf("%d",w+i); build(1,1,n); for(int i=1;i<=m;i++) { int opt,l,r,x; scanf("%d%d%d",&opt,&l,&r); if(opt==1)scanf("%d",&x),update(1,1,n,l,r,(Node){F(x),F(x+1)}); else printf("%d\n",(query(1,1,n,l,r)+mod)%mod); } } ```