[2019牛客多校第二场][E. MAZE]

题目链接：https://ac.nowcoder.com/acm/contest/882/E

题目大意：有一个(n imes m)的01矩阵，一开始可以从第一行的一个点出发，每次可以向左、向右、向下移动一格且不能回头。中途会有一些点变为障碍物（用1表示），或者从障碍物变回可以通过的格子，同时还需要处理询问：从((1,a))出发，走到((n,b))的方案数有多少种。(nleq 50000, mleq 10)

题解：设(f(i,j))为走到((i,j))的方案数，且第(i)行里包含点((i,j))的区间为([l,r])，则有(f(i,j)=sum_{k=l}^{r}f(i-1,k))，这里的(k)就代表着从前一行的第(k)列走下来。可以发现这个转移方程可以转换成一个矩阵形式，即((f(i,1),f(i,2),...,f(i,m))=(f(i-1,1),f(i-1,2),...,f(i-1,m))cdot A)其中(A)为状态转移矩阵。求从第(i-1)行到第(i)行的转移矩阵是可以用(O(m^2))的时间复杂度来实现的。而最后一行的答案就是第一行的状态矩阵乘上这(n)行转移矩阵的乘积。在本题中，由于给出了起点和终点，所以若设这(n)行转移矩阵的乘积为(A)，则答案就是(A(a,b))。用线段树维护每行的矩阵以及区间的矩阵乘积即可。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define N 50001
  4 #define LL long long
  5 #define MOD 1000000007
  6 LL n,m,q,op,x,y,a[N][11];
  7 struct Matrix
  8 {
  9     LL n,m;
 10     LL f[11][11];
 11     void init(LL nn,LL mm)
 12       {
 13       n=nn,m=mm;
 14       for(LL i=1;i<=n;i++)
 15         for(LL j=1;j<=m;j++)
 16           f[i][j]=0;
 17       }
 18     void set_E(LL nn)
 19       {
 20       n=m=nn;
 21       for(LL i=1;i<=n;i++)
 22         for(LL j=1;j<=n;j++)
 23           f[i][j]=i==j;
 24       }
 25     Matrix operator *(const Matrix &t)const
 26       {
 27       Matrix res;
 28       res.init(n,t.m);
 29       for(LL i=1;i<=n;i++)
 30         for(LL j=1;j<=t.m;j++)
 31           for(LL k=1;k<=m;k++)
 32             (res.f[i][j]+=f[i][k]*t.f[k][j]%MOD)%=MOD;
 33       return res;
 34       }
 35     void get(LL i,LL mm)
 36       {
 37       init(mm,mm);
 38       LL l=1,r=1;
 39       for(LL j=1;j<=m;j++)
 40         {
 41         if(a[i][j]==1)
 42           {
 43           l=r=j+1;
 44           continue;
 45           }
 46         while(r<=m && a[i][r]==a[i][l])r++;r--;
 47         for(LL k=l;k<=r;k++)
 48           f[k][j]++;
 49         }
 50       }
 51 };
 52 struct Segment_Tree
 53 {
 54     struct rua
 55       {
 56       LL l,r;
 57       Matrix v;
 58       }t[N<<2];
 59     void Update(LL x)
 60       {
 61       t[x].v=t[x*2].v*t[x*2+1].v;
 62       }
 63     void Build(LL l,LL r,LL x)
 64       {
 65       t[x].l=l,t[x].r=r;
 66       if(l==r)
 67         {
 68         t[x].v.get(l,m);
 69         return;
 70         }
 71       LL mid=l+r>>1;
 72       Build(l,mid,x*2);
 73       Build(mid+1,r,x*2+1);
 74       Update(x);
 75       }
 76     void Change(LL x,LL y)
 77       {
 78       LL l=t[x].l,r=t[x].r;
 79       LL mid=l+r>>1;
 80       if(l==y && y==r)
 81         {
 82         t[x].v.get(y,m);
 83         return;
 84         }
 85       if(y<=mid)Change(x*2,y);
 86       else Change(x*2+1,y);
 87       Update(x);
 88       }
 89     Matrix Query(LL L,LL R,LL x)
 90       {
 91       LL l=t[x].l,r=t[x].r;
 92       LL mid=l+r>>1;
 93       if(L<=l && r<=R)return t[x].v;
 94       Matrix res;
 95       res.set_E(m);
 96       if(L<=mid)res=res*Query(L,R,x*2);
 97       if(R>mid)res=res*Query(L,R,x*2+1);
 98       return res;
 99       }
100 }T;
101 LL get()
102 {
103     char ch=getchar();
104     while(ch!='0' && ch!='1')
105       ch=getchar();
106     return ch-'0';
107 }
108 int main()
109 {
110     scanf("%lld%lld%lld",&n,&m,&q);
111     for(LL i=1;i<=n;i++)
112       for(LL j=1;j<=m;j++)
113         a[i][j]=get();
114     T.Build(1,n,1);
115     while(q--)
116       {
117       scanf("%lld%lld%lld",&op,&x,&y);
118       if(op==1)
119         {
120         a[x][y]^=1;
121         T.Change(1,x);
122         }
123       if(op==2)
124         {
125         Matrix tmp=T.Query(1,n,1);
126         printf("%lld
",tmp.f[x][y]);
127         }
128       }
129     return 0; 
130 }

View Code