Codeforce 1252K - Addition Robot 参考blog：https://blog.csdn.net/weixin_43731933/article/details/102772187 本来思路也大致相同，但是没往矩阵那一块想，反而自己想用一个数对就好了，结果自己半天在那证明他的结合性，从而可以用线段树解决。往矩阵的方向想，思路会清晰很多，最后ac代码也是参考上面博客的。
#include <bits/stdc++.h> #define LL long long const int N = 2e5+10; using namespace std; typedef long long ll; typedef unsigned long long ull; const int mod=1e9+7; struct M { ll m[2][2]; M(){ memset(m,0,sizeof(m)); } }A,B; #define ls ((rt)<<1) #define rs ((rt)<<1|1) #define mid ((l)+(r) >>1) //这里的define不错，学学，线段树会方便很多 M tr[N<<2][2]; int lazy[N<<2]; char s[N]; M mul(M a,M b) { M res; for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { for(int k=0;k<2;k++) res.m[i][j]=(res.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod; } } return res; } void push_up(int rt) //这个函数就是其他函数里结尾都有的，用来更新当前节点的信息 { tr[rt][0]=mul(tr[ls][0],tr[rs][0]); tr[rt][1]=mul(tr[ls][1],tr[rs][1]); return; } void push_down(int rt)//往下传懒惰标记 { if(lazy[rt]) { swap(tr[ls][0],tr[ls][1]); swap(tr[rs][0],tr[rs][1]); lazy[ls]^=1;//位运算会快一点吗？ lazy[rs]^=1; lazy[rt]=0; } return; } void build(int rt,int l,int r) { if(l==r) { if(s[l]=='A') { tr[rt][0]=A; tr[rt][1]=B; } else { tr[rt][0]=B; tr[rt][1]=A; } return; } build(ls,l,mid); build(rs,mid+1,r); push_up(rt); return; } void update(int rt,int l,int r,int L,int R)//L,R是要修改的区间 { if(L<=l&&r<=R) { swap(tr[rt][0],tr[rt][1]); lazy[rt]^=1; return; } push_down(rt); if(L<=mid) update(ls,l,mid,L,R); if(R>mid) update(rs,mid+1,r,L,R); push_up(rt); return; } void query(int rt,int l,int r,int L,int R,M & tmp)//L,R是要询问答案的区间 { if(L<=l&&r<=R) { tmp=mul(tmp,tr[rt][0]); return; } push_down(rt); if(L<=mid) query(ls,l,mid,L,R,tmp); if(R>mid) query(rs,mid+1,r,L,R,tmp); push_up(rt); } int main() { int n,q; scanf("%d%d",&n,&q); scanf("%s",s+1); int op; int L,R; int a,b; A.m[0][0]=A.m[1][0]=A.m[1][1]=B.m[0][0]=B.m[0][1]=B.m[1][1]=1; build(1,1,n); while(q--) { scanf("%d",&op); if(op==1) { scanf("%d%d",&L,&R); update(1,1,n,L,R); } else { scanf("%d%d",&L,&R); scanf("%d%d",&a,&b); M tmp; tmp.m[0][0]=tmp.m[1][1]=1; query(1,1,n,L,R,tmp); M ans; ans.m[0][0]=a;ans.m[0][1]=b; ans=mul(ans,tmp); printf("%lld %lld\n",ans.m[0][0],ans.m[0][1]); } } return 0; }