hdu 5068 线段树加+dp

时间：2021-12-13 20:05:31

这题说的是 有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=; i<; ++i)

            for(int j=; j<; ++j)

                if(star[mid][i][j]){

                  value[o].M[][]=(value[o].M[][] + value[o*].M[i][] * value[o*+].M[][j] % mod )%mod;

                   value[o].M[][]=(value[o].M[][] + value[o*].M[i][] * value[o*+].M[][j]%mod )%mod;

                   value[o].M[][]=(value[o].M[][] + value[o*].M[i][] * value[o*+].M[][j]%mod )%mod;

                   value[o].M[][]=(value[o].M[][] + value[o*].M[i][] * value[o*+].M[][j]%mod )%mod;

                }
#include <iostream>

#include <cstdio>

#include <string.h>

using namespace std;

typedef __int64 ll;

const int maxn = ;

const ll mod = ;

int loc,x,y;

struct Matx{

   ll M[][];

}P;

bool star[maxn+][][];

void maintain(int mid ,Matx &A,Matx B){

         Matx ans;

         memset(ans.M,,sizeof(ans.M));

           for(int i=; i<; ++i)

            for(int j=; j<; ++j)

                if(star[mid][i][j]){

                   ans.M[][]=(ans.M[][] + A.M[i][] * B.M[][j] )%mod;

                   ans.M[][]=(ans.M[][] + A.M[i][] * B.M[][j] )%mod;

                   ans.M[][]=(ans.M[][] + A.M[i][] * B.M[][j] )%mod;

                   ans.M[][]=(ans.M[][] + A.M[i][] * B.M[][j] )%mod;

                }

          for(int i=; i<; ++i)

            for(int j=; j<; ++j)

              A.M[i][j]=ans.M[i][j];

}

struct Itree{

    Matx value[maxn*];

    void tain(int o,int mid){

         memset(value[o].M,,sizeof(value[o].M));

           for(int i=; i<; ++i)

            for(int j=; j<; ++j)

                if(star[mid][i][j]){

                  value[o].M[][]=(value[o].M[][] + value[o*].M[i][] * value[o*+].M[][j] % mod )%mod;

                   value[o].M[][]=(value[o].M[][] + value[o*].M[i][] * value[o*+].M[][j]%mod )%mod;

                   value[o].M[][]=(value[o].M[][] + value[o*].M[i][] * value[o*+].M[][j]%mod )%mod;

                   value[o].M[][]=(value[o].M[][] + value[o*].M[i][] * value[o*+].M[][j]%mod )%mod;

                }

    }

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

         if(L==R){

           value[o].M[][]=;

           value[o].M[][]=;

           value[o].M[][]=;

           value[o].M[][]=;

             for(int i=; i<; ++i)

                for(int j=; j<;  ++j)

                  star[L][i][j]=true;

             return ;

         }

         int mid= (L+R)/;

         build( o* , L , mid );

         build( o*+ , mid+ , 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)/;

            if(loc<=mid) update(o*,L,mid);

            else update(o*+,mid+,R);

            tain(o, mid);

    }

    void query(int o, int L, int R){

            if( (L>=x&&R<=y) ){

                if(loc==){

                    P=value[o];loc=;

                }else{

                    maintain(L-,P,value[o]);

                }

                return ;

            }

            int mid = (L+R)/;

            if(x<=mid)

                query(o*,L,mid);

            if(y>mid)

                query(o*+,mid+,R);

    }

}T;

int main()

{

     int n,m;

     while(scanf("%d%d",&n,&m)==){

        T.build(,,n);

        for(int i=; i<m; ++i){

             loc=;

             int op;

             scanf("%d",&op);

             if(op==) {

                    scanf("%d%d",&x,&y);

                    T.query(,,n);

                    ll ans=;

                    for(int i=; i<; ++i)

                         for(int j=; j<; ++j)

                          ans=(ans+ P.M[i][j])%mod;

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

             }else{

                 scanf("%d%d%d",&loc,&x,&y);

                 x--; y--;

                 T.update(,,n);

             }

        }

     }

    return ;

}

相关文章