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

題意：給你n層樓，每層樓有兩個門，

m個操作 Q = 1 ?表示 第 x 層樓 第y個門到第x+1層樓的第z個門的路改變其狀態(tài)（初始每條路都可以走的）

* ? ? ? ? ? ?Q = 0 ? 表示詢問第x層樓到第y層樓的方式有多少種

題解：線段數(shù) + 矩陣乘法 ? ? ??

因為只有兩個門所以我們可以把第x層樓到第x+1層樓標(biāo)記狀態(tài)

/**單純的從某層樓到某層樓，可以用一個遞推，然后可以演化成矩陣如下* 0 1* ————*0 |1 1*1 |1 1*如果在更新的話只需更改某個門到某個門的標(biāo)記即可，即異或1，就可以改變其狀態(tài)，即矩陣的值有所改變；*此題比較裸地線段樹（插點問線問題）*根據(jù)矩陣的結(jié)合律計算即可 **/#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> 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; }

總結(jié)

以上是生活随笔為你收集整理的hdu-5068 Harry And Math Teacher的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。