hdu6155 Subsequence Count

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, m, T, uu, vv, ww;
const int mod=1000000007;
char ss[100005];
struct Matrix{
	int ma[3][3];
	Matrix operator * (const Matrix &b)const{
		Matrix re;
		for(int i=0; i<3; i++)
			for(int j=0; j<3; j++){
				re.ma[i][j] = 0;
				for(int k=0; k<3; k++)
					re.ma[i][j] = (re.ma[i][j] + (ll)ma[i][k]*b.ma[k][j]) % mod;
			}
		return re;
	}
	void reverse(){
		swap(ma[0], ma[1]);
		for(int i=0; i<3; i++)	swap(ma[i][0], ma[i][1]);
	}
}mat[2], dan;
struct SGT{
	Matrix mul[400005];
	int rev[400005];
	void build(int o, int l, int r){
		rev[o] = 0;
		if(l==r)	mul[o] = mat[ss[l]-'0'];
		else{
			int mid=(l+r)>>1;
			int lson=o<<1;
			int rson=lson|1;
			if(l<=mid)	build(lson, l, mid);
			if(mid<r)	build(rson, mid+1, r);
			mul[o] = mul[lson] * mul[rson];
		}
	}
	void pushDown(int o, int lson, int rson){
		rev[lson] ^= 1;
		rev[rson] ^= 1;
		mul[lson].reverse();
		mul[rson].reverse();
		rev[o] = 0;
	}
	void update(int o, int l, int r, int x, int y){
		if(l>=x && r<=y){
			rev[o] ^= 1;
			mul[o].reverse();
		}
		else{
			int mid=(l+r)>>1;
			int lson=o<<1;
			int rson=lson|1;
			if(rev[o])	pushDown(o, lson, rson);
			if(x<=mid)	update(lson, l, mid, x, y);
			if(mid<y)	update(rson, mid+1, r, x, y);
			mul[o] = mul[lson] * mul[rson];
		}
	}
	Matrix query(int o, int l, int r, int x, int y){
		if(l>=x &&r<=y)	return mul[o];
		else{
			int mid=(l+r)>>1;
			int lson=o<<1;
			int rson=lson|1;
			Matrix ans=dan;
			if(rev[o])	pushDown(o, lson, rson); 
			if(x<=mid)	ans = ans * query(lson, l, mid, x, y);
			if(mid<y)	ans = ans * query(rson, mid+1, r, x, y);
			return ans;
		}
	} 
}sgt;
int main(){
	mat[0].ma[0][0] = 1; mat[0].ma[0][1] = 1; mat[0].ma[0][2] = 1; 
	mat[0].ma[1][0] = 0; mat[0].ma[1][1] = 1; mat[0].ma[1][2] = 0; 
	mat[0].ma[2][0] = 0; mat[0].ma[2][1] = 0; mat[0].ma[2][2] = 1; 
	mat[1].ma[0][0] = 1; mat[1].ma[0][1] = 0; mat[1].ma[0][2] = 0; 
	mat[1].ma[1][0] = 1; mat[1].ma[1][1] = 1; mat[1].ma[1][2] = 1; 
	mat[1].ma[2][0] = 0; mat[1].ma[2][1] = 0; mat[1].ma[2][2] = 1; 
	for(int i=0; i<3; i++)
		for(int j=0; j<3; j++)
			if(i==j)	dan.ma[i][j] = 1;
			else	dan.ma[i][j] = 0;
	cin>>T;
	while(T--){
		cin>>n>>m; 
		scanf("%s", ss+1);
		sgt.build(1, 1, n);
		while(m--){
			scanf("%d %d %d", &ww, &uu, &vv);
			if(ww==1)	sgt.update(1, 1, n, uu, vv);
			else{
				Matrix tmp=sgt.query(1, 1, n, uu, vv);
				printf("%d
", (tmp.ma[0][2]+tmp.ma[1][2]) % mod); 
			}
		}
	}
	return 0;
}