本文共 2458 字，大约阅读时间需要 8 分钟。
题意：给你n层楼，每层楼有两个门，
m个操作 Q = 1 表示 第 x 层楼 第y个门到第x+1层楼的第z个门的路改变其状态（初始每条路都可以走的）
* Q = 0 表示询问第x层楼到第y层楼的方式有多少种
题解：线段数 + 矩阵乘法
因为只有两个门所以我们可以把第x层楼到第x+1层楼标记状态
/**单纯的从某层楼到某层楼，可以用一个递推，然后可以演化成矩阵如下 * 0 1 * ———— *0 |1 1 *1 |1 1 *如果在更新的话只需更改某个门到某个门的标记即可，即异或1，就可以改变其状态，即矩阵的值有所改变； *此题比较裸地线段树（插点问线问题） *根据矩阵的结合律计算即可**/#include#include #include #include #include using namespace std;typedef __int64 LL;const LL mod = 1000000007;#define M 50010#define lson(st) (st<<1)#define rson(st) ((st<<1)|1)int x,y,z;struct matrix{ LL m[2][2]; matrix(){memset(m,0,sizeof(m));} matrix operator * (const matrix &a) const{ matrix c; for(int i = 0;i < 2;i ++) for(int j = 0;j < 2;j ++) for(int k = 0;k < 2;k ++) c.m[i][j] = (c.m[i][j] + m[i][k]*a.m[k][j]) % mod; return c; }};struct Node{ matrix s; int l,r;}node[M<<3];void Pushup(int st){ node[st].s= node[lson(st)].s * node[rson(st)].s;}void build(int l,int r,int st){ node[st].l = l; node[st].r = r; if(l == r){ for(int i = 0;i < 2;i++) for(int j = 0;j < 2;j++) node[st].s.m[i][j] = 1; return ; } int mid = (l + r) >> 1; build(l,mid,lson(st)); build(mid+1,r,rson(st)); Pushup(st);}void update(int x,int st){ if(node[st].l == node[st].r){ node[st].s.m[y][z] ^= 1; return ; } int mid = (node[st].l + node[st].r) >> 1; if(x <= mid) update(x,lson(st)); else update(x,rson(st)); Pushup(st);}matrix Query(int L,int R,int st){ if(node[st].l >= L && node[st].r <= R) return node[st].s; matrix ans; ans.m[0][0] = ans.m[1][1] = 1; int mid = (node[st].l + node[st].r) >> 1; if(L <= mid) ans = ans * Query(L,R,lson(st)); if(R > mid) ans = ans * Query(L,R,rson(st)); return ans;}int main(){ int n,m,q; while(~scanf("%d%d",&n,&m)){ build(1,n-1,1); for(int i = 0;i < m;i++){ cin >> q; if(q == 1) { cin >> x >> y >> z; y--,z--; update(x,1); } else { cin >> x >> y; matrix res = Query(x,y-1,1); LL ans = 0; for(int k = 0;k < 2;k++) for(int j = 0;j < 2;j++) ans = (ans + res.m[k][j]) % mod; cout << ans << endl; } } } return 0;}
转载地址：http://kcsgi.baihongyu.com/