http://acm.hdu.edu.cn/showproblem.php?pid=6155
第一次做矩阵快速幂套线段树的题，感觉好神奇
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+5,mo=1e9+7; struct NODE { long long a[3][3]; }t1,t2,be; NODE mult(NODE a,NODE b) { NODE c; memset(c.a,0,sizeof(c.a)); for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { for(int k=0;k<3;k++) { c.a[i][j]+=a.a[i][k]*b.a[k][j]; if(c.a[i][j]>=mo) c.a[i][j]%=mo; } } } return c; } NODE seg[4*maxn]; bool lazy[4*maxn]; int num[maxn]; void pushup(int node) { seg[node]=mult(seg[node<<1],seg[node<<1|1]); } void change(NODE &a) { for(int i=0;i<3;i++) swap(a.a[i][0],a.a[i][1]); for(int i=0;i<3;i++) swap(a.a[0][i],a.a[1][i]); } void pushdown(int node) { if(lazy[node]) { lazy[node<<1]=!lazy[node<<1]; lazy[node<<1|1]=!lazy[node<<1|1]; change(seg[node<<1]); change(seg[node<<1|1]); lazy[node]=0; } } void build(int l,int r,int node) { lazy[node]=0; if(l==r) { seg[node]=num[l]?t2:t1; return ; } int m=(l+r)>>1; build(l,m,node<<1); build(m+1,r,node<<1|1); pushup(node); return ; } void update(int le,int ri,int l,int r,int node) { if(l>=le&&r<=ri) { lazy[node]=!lazy[node]; change(seg[node]); return ; } pushdown(node); int m=(l+r)>>1; if(m>=le) update(le,ri,l,m,node<<1); if(m<ri) update(le,ri,m+1,r,node<<1|1); pushup(node); return ; } NODE query(int le,int ri,int l,int r,int node) { if(l>=le&&r<=ri) { return seg[node]; } pushdown(node); NODE sum; memset(sum.a,0,sizeof sum.a); for(int i=0;i<3;i++) sum.a[i][i]=1; int m=(l+r)>>1; if(m>=le) sum=mult(sum,query(le,ri,l,m,node<<1)); if(m<ri) sum=mult(sum,query(le,ri,m+1,r,node<<1|1)); return sum; } int ch[maxn]; int main() { t1.a[0][0]=t1.a[1][0]=t1.a[2][0]=t1.a[1][1]=t1.a[2][2]=1; t2.a[0][0]=t2.a[0][1]=t2.a[1][1]=t2.a[2][1]=t2.a[2][2]=1; be.a[0][2]=1; int T,n,q,ty,l,r; NODE ans; cin>>T; while(T--) { cin>>n>>q; for(int i=1;i<=n;i++) scanf(" ",&num[i]); build(1,n,1); while(q--) { scanf("%d %d %d",&ty,&l,&r); if(ty-1) { ans=mult(be,query(l,r,1,n,1)); printf("%lld\n",(ans.a[0][0]+ans.a[0][1])%mo); } else { update(l,r,1,n,1); } } } return 0; }
