首页 > 代码库 > hdu 5068 线段树加+dp
hdu 5068 线段树加+dp
这题说的是 有n 层每层 有两个门 每个门 可以到达上一层的两个门，然后求从a 层到达b 层的方案总数， 不能后退， 在同一层中不能从第一个门到达另一层
我们只要我们可以对于每个 区间内 有dp[o][2][2] , 表示 在这个区间中 从区间起始到达区间末尾 的两个门分别设 a1,a2, b1,b2, dp[o][0][0],和dp[o][0][1],表示从从a1到b1 和 a2 到 b1 的方案总数 然后同理dp[o][1][0]dp[o][1][1],
得到转移 通过线段树去优化他 得到转移 一旦ij 两地相通那么显然 i这个点 的 在前面这个区间的a1 a2 相应的乘上 后面 这个区间在 j 这个位置开始的方案总数， 得到他们在总区间结束时的在 b1上有多少个方案从前面区间的 a1 和a2 过来，通过这样得到整个区间的值
for(int i=0; i<2; ++i) for(int j=0; j<2; ++j) if(star[mid][i][j]){ value[o].M[0][0]=(value[o].M[0][0] + value[o*2].M[i][0] * value[o*2+1].M[0][j] % mod )%mod; value[o].M[0][1]=(value[o].M[0][1] + value[o*2].M[i][1] * value[o*2+1].M[0][j]%mod )%mod; value[o].M[1][0]=(value[o].M[1][0] + value[o*2].M[i][0] * value[o*2+1].M[1][j]%mod )%mod; value[o].M[1][1]=(value[o].M[1][1] + value[o*2].M[i][1] * value[o*2+1].M[1][j]%mod )%mod;
}
#include <iostream>#include <cstdio>#include <string.h>using namespace std;typedef __int64 ll;const int maxn = 50005;const ll mod = 1000000007;int loc,x,y;struct Matx{ ll M[2][2];}P;bool star[maxn+5][2][2];void maintain(int mid ,Matx &A,Matx B){ Matx ans; memset(ans.M,0,sizeof(ans.M)); for(int i=0; i<2; ++i) for(int j=0; j<2; ++j) if(star[mid][i][j]){ ans.M[0][0]=(ans.M[0][0] + A.M[i][0] * B.M[0][j] )%mod; ans.M[0][1]=(ans.M[0][1] + A.M[i][1] * B.M[0][j] )%mod; ans.M[1][0]=(ans.M[1][0] + A.M[i][0] * B.M[1][j] )%mod; ans.M[1][1]=(ans.M[1][1] + A.M[i][1] * B.M[1][j] )%mod; } for(int i=0; i<2; ++i) for(int j=0; j<2; ++j) A.M[i][j]=ans.M[i][j];}struct Itree{ Matx value[maxn*4]; void tain(int o,int mid){ memset(value[o].M,0,sizeof(value[o].M)); for(int i=0; i<2; ++i) for(int j=0; j<2; ++j) if(star[mid][i][j]){ value[o].M[0][0]=(value[o].M[0][0] + value[o*2].M[i][0] * value[o*2+1].M[0][j] % mod )%mod; value[o].M[0][1]=(value[o].M[0][1] + value[o*2].M[i][1] * value[o*2+1].M[0][j]%mod )%mod; value[o].M[1][0]=(value[o].M[1][0] + value[o*2].M[i][0] * value[o*2+1].M[1][j]%mod )%mod; value[o].M[1][1]=(value[o].M[1][1] + value[o*2].M[i][1] * value[o*2+1].M[1][j]%mod )%mod; } } void build(int o, int L, int R){ if(L==R){ value[o].M[0][0]=1; value[o].M[0][1]=0; value[o].M[1][0]=0; value[o].M[1][1]=1; for(int i=0; i<2; ++i) for(int j=0; j<2; ++j) star[L][i][j]=true; return ; } int mid= (L+R)/2; build( o*2 , L , mid ); build( o*2+1 , mid+1 , R ); tain(o,mid); } void update(int o, int L, int R){ if(L==R){ star[L][x][y]=star[L][x][y]==false; return ; } int mid=(L+R)/2; if(loc<=mid) update(o*2,L,mid); else update(o*2+1,mid+1,R); tain(o, mid); } void query(int o, int L, int R){ if( (L>=x&&R<=y) ){ if(loc==0){ P=value[o];loc=1; }else{ maintain(L-1,P,value[o]); } return ; } int mid = (L+R)/2; if(x<=mid) query(o*2,L,mid); if(y>mid) query(o*2+1,mid+1,R); }}T;int main(){ int n,m; while(scanf("%d%d",&n,&m)==2){ T.build(1,1,n); for(int i=0; i<m; ++i){ loc=0; int op; scanf("%d",&op); if(op==0) { scanf("%d%d",&x,&y); T.query(1,1,n); ll ans=0; for(int i=0; i<2; ++i) for(int j=0; j<2; ++j) ans=(ans+ P.M[i][j])%mod; printf("%I64d\n",ans); }else{ scanf("%d%d%d",&loc,&x,&y); x--; y--; T.update(1,1,n); } } } return 0;}
hdu 5068 线段树加+dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。