题意 ：每层都有2个门，每个门后面都能通向下一层的两个门，有两个操作 ，第一个 问 从a层到 b层的方法数，第二个 修改 其中某门通向某门的状态。
线段树单点更新，矩阵连通性构造 离散数学里有讲。
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <map> #include <cstdlib> #include <list> #include <set> #include <queue> #include <stack> #include <math.h> using namespace std; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 typedef long long LL; const LL maxn = 55555; const LL mod = 1000000007; struct Node { LL x1, x2, x3, x4; }; Node ans; Node node[maxn << 2]; Node gao(Node a, Node b) { Node t; t.x1 = a.x1*b.x1%mod + a.x2*b.x3%mod; t.x2 = a.x1*b.x2%mod + a.x2*b.x4%mod; t.x3 = a.x3*b.x1%mod + a.x4*b.x3%mod; t.x4 = a.x3*b.x2%mod + a.x4*b.x4%mod; return t; } void up(LL rt) { node[rt] = gao(node[rt<<1],node[rt<<1|1]); } void build(LL l, LL r, LL rt) { if (l == r){ node[rt].x1 = 1; node[rt].x2 = 1; node[rt].x3 = 1; node[rt].x4 = 1; return; } LL mid = (l + r) >> 1; build(lson); build(rson); up(rt); } void init() { ans.x1 = 1; ans.x2 = 0; ans.x3 = 0; ans.x4 = 1; } void update(LL k, LL i, LL l, LL r, LL rt) { if (l == r){ switch (i){ case 1:node[rt].x1 ^= 1; break; case 2:node[rt].x2 ^= 1; break; case 3:node[rt].x3 ^= 1; break; default:node[rt].x4 ^= 1; } return; } LL mid = (l + r) >> 1; if (k <= mid) update(k, i, lson); if (k > mid) update(k, i, rson); up(rt); } void ask(LL L, LL R, LL l, LL r, LL rt) { if (L <= l&&r <= R){ ans = gao(ans, node[rt]); return; } LL mid = (l + r) >> 1; if (L <= mid) ask(L, R, lson); if (R > mid) ask(L, R, rson); } void output() { LL sum; sum = (ans.x1 + ans.x2)%mod + (ans.x3 + ans.x4)%mod; sum%=mod; printf("%I64d ", sum); } int main() { LL a, b, c, t, n, m; while (cin >> n >> m){ build(1, n - 1, 1); for (LL i = 0; i < m; i++){ scanf("%I64d", &t); if (t == 0){ scanf("%I64d%I64d", &a, &b); if (a == b){ printf("0 "); continue; } init(); ask(a, b - 1, 1, n - 1, 1); output(); } else{ scanf("%I64d%I64d%I64d", &a, &b, &c); if (b == 1 && c == 1) update(a, 1, 1, n - 1, 1); if (b == 1 && c == 2) update(a, 2, 1, n - 1, 1); if (b == 2 && c == 1) update(a, 3, 1, n - 1, 1); if (b == 2 && c == 2) update(a, 4, 1, n - 1, 1); } } } return 0; }