http://acm.hdu.edu.cn/showproblem.php?pid=5068

题意给的略不清晰

m个询问：从i层去j层的方法数(求连段乘积)或者修改从x层y门和x+1层z门的状态反转(更新只需更新一个节点的矩阵)

直接贴题解

我们可以把第i层跟第i+1层之间楼梯的通断性构造成一个2*2的通断性矩阵，1表示通，0表示不通。那么从第a层到第b层，就是将a到b-1的通断性矩阵连乘起来，然后将得到的答案矩阵上的每个元素加起来即为方案数。想到矩阵的乘法是满足结合律的，那么我们可以用线段树来维护矩阵的乘积。每次我们只会修改某一个楼梯的通断性，所以就只是简单的线段树单点更新，成段求乘积而已。

整体复杂度2∗2∗2∗nlogn

线段树维护矩阵乘积

初始化时要当成所有门是完好的

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <map>

#include <iostream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define clr0(x) memset(x,0,sizeof(x))

typedef long long LL;

const int maxn = 30010;

#define M 50005

#define N 11

#define P 1000000007

using namespace std;

struct node{

    int L,R;

    int num[2][2];

}tree[M<<2];

void up(node &A,node &B,node &C){

    int i,j,k;

    for(i=0;i<2;i++)

        for(j=0;j<2;j++){

            A.num[i][j]=0;

            for(k=0;k<2;k++){

                A.num[i][j]+=(1LL*B.num[i][k]*C.num[k][j])%P;

            }

            A.num[i][j]%=P;

        }

}

void build(int L,int R,int p){

    tree[p].L=L,tree[p].R=R;

    if(L==R){

        tree[p].num[0][0]=1; tree[p].num[0][1]=1;

        tree[p].num[1][0]=1; tree[p].num[1][1]=1;

        return;

    }

    int mid=(L+R)>>1;

    build(L,mid,2*p);

    build(mid+1,R,2*p+1);

    up(tree[p],tree[2*p],tree[2*p+1]);

}

node query(int L,int R,int p){

    if(tree[p].L==L&&tree[p].R==R){

        return tree[p];

    }

    int mid=(tree[p].L+tree[p].R)>>1;

    if(R<=mid)return query(L,R,2*p);

    else if(L>mid)return query(L,R,2*p+1);

    else{

        node tmp1=query(L,mid,2*p);

        node tmp2=query(mid+1,R,2*p+1);

        node res;

        up(res,tmp1,tmp2);

        return res;

    }

}

void update(int x,int a,int b,int p){

    if(tree[p].L==tree[p].R){

        tree[p].num[a][b]^=1;

        return ;

    }

    int mid=(tree[p].L+tree[p].R)>>1;

    if(x<=mid)update(x,a,b,2*p);

    else update(x,a,b,2*p+1);

    up(tree[p],tree[2*p],tree[2*p+1]);

}

int main(){

    int n,m,i,j,k,a,b,x,y,z;

    while(~RD2(n,m)){

        build(1,n-1,1);

        while(m--){

            RD(k);

            if(k==0){

                RD2(a,b);

                node res=query(a,b-1,1);

                int ans=(1LL*res.num[0][0]+res.num[0][1]+res.num[1][0]+res.num[1][1])%P;

                printf("%d\n",ans);

            }else{

                RD3(x,y,z);

                update(x,y-1,z-1,1);

            }

        }

    }

    return 0;

}