记录编号	142299	评测结果	AAAAAAAAAA
题目名称	[HDOJ5068]哈利波特与数学老师	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.325 s
提交时间	2014-12-07 12:05:03	内存使用	7.56 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MOD=1000000007;
const int SIZEN=50010;
class MATRIX{
public:
	int n,m;
	LL s[2][2];
	void print(void){
		cout<<"size: "<<n<<" "<<m<<endl;
		for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<s[i][j]<<" ";}cout<<endl;}cout<<endl;
	}
	void make_intact(void){
		n=m=2;
		s[0][0]=s[0][1]=s[1][0]=s[1][1]=1;
	}
	void make_one(void){
		n=m=2;
		s[0][0]=s[1][1]=1;
		s[0][1]=s[1][0]=0;
	}
	LL sum(void){
		LL ans=0;
		for(int i=0;i<n;i++) for(int j=0;j<m;j++) ans+=s[i][j];
		return ans%MOD;
	}
};
MATRIX I2;//2*2单位矩阵
MATRIX operator * (MATRIX a,MATRIX b){
	MATRIX c;
	c.n=a.n,c.m=b.m;
	for(int i=0;i<c.n;i++){
		for(int j=0;j<c.m;j++){
			c.s[i][j]=0;
			for(int k=0;k<a.m;k++){
				c.s[i][j]+=(a.s[i][k]*b.s[k][j])%MOD;
				c.s[i][j]%=MOD;
			}
		}
	}
	return c;
}
class NODE{
public:
	int a,b;//范围
	int lc,rc;//儿子
	MATRIX D;//矩阵
	#define a(x) Tree[x].a
	#define b(x) Tree[x].b
	#define lc(x) Tree[x].lc
	#define rc(x) Tree[x].rc
	#define D(x) Tree[x].D
}Tree[SIZEN*2];
#define Root 1
int tot;
void update(int x){
	if(!x) return;
	if(!lc(x)) return;
	D(x)=D(lc(x))*D(rc(x));
}
int build(int l,int r){
	int p=++tot;
	a(p)=l,b(p)=r,D(p).make_intact();
	if(l<r){
		int mid=(l+r)/2;
		lc(p)=build(l,mid);
		rc(p)=build(mid+1,r);
		update(p);
	}
	else lc(p)=rc(p)=0;
	return p;
}
void change(int rt,int x,MATRIX &t){
	if(!rt) return;
	if(a(rt)>x||b(rt)<x) return;
	if(a(rt)==x&&b(rt)==x) D(rt)=t;
	else{
		change(lc(rt),x,t);
		change(rc(rt),x,t);
		update(rt);
	}
}
MATRIX query(int rt,int l,int r){
	if(!rt) return I2;
	if(a(rt)>r||b(rt)<l) return I2;
	if(a(rt)>=l&&b(rt)<=r) return D(rt);
	return query(lc(rt),l,r)*query(rc(rt),l,r);
}
MATRIX stair[SIZEN];
bool work(void){
	int N,M;
	if(scanf("%d%d",&N,&M)==EOF) return false;
	for(int i=1;i<=N;i++) stair[i].make_intact();
	tot=0;
	build(1,N);
	int op,x,y,z;
	for(int i=1;i<=M;i++){
		scanf("%d",&op);
		if(!op){
			scanf("%d%d",&x,&y);//x~y层
			MATRIX ans=query(Root,x,y-1);
			printf("%I64d\n",ans.sum());
		}
		else{
			scanf("%d%d%d",&x,&y,&z);
			stair[x].s[y-1][z-1]^=1;
			change(Root,x,stair[x]);
		}
	}
	return true;
}
int main(){
	freopen("harryandmathteacher.in","r",stdin);
	freopen("harryandmathteacher.out","w",stdout);
	I2.make_one();
	while(work());
	return 0;
}