题解 | #智乃的双塔问题#

题目链接：https://ac.nowcoder.com/acm/contest/19483/E
题目一上手，很容易想到动态规划。用dp[i][0]表示从第1层到达第i层左边的方案数，dp[i][1]表示从第1层到达第i层右边的方案数：
当梯子为'/'时，

    dp[i][1]=dp[i-1][0]+dp[i-1][1]
    dp[i][0]=dp[i-1][0]

当梯子为'\'时

    dp[i][1]=dp[i-1][1]
    dp[i][0]=dp[i-1][0]+dp[i-1][1]

初值dp[1][0]=dp[1][1]=1
这时可以发现，该转移方程可写成矩阵形式
为了表示初位置是左还是右，我们采用2 * 2的矩阵来表示。

$图片说明$

其中t是从第i-1层到第i层的转移矩阵。
当梯子为'/'时，
$图片说明$
当梯子为'\'时，
$图片说明$
这样就能记录从第1层到第i层四种方式(左到左、左到右、右到左、右到右)的方法数啦
注意：
1.在计算hs到ht的方法数时，需要用1到ht的方法减去1到hs的方法，即presum[ht]/presum[hs]（注意不是hs-1）。这里需要把除变成乘，通过求逆矩阵实现。
2.矩阵乘法不满*** 换律。由于 1到ht方法presum[ht]= 1到hs方法presum[hs] *hs到ht的一堆转移矩阵t ，因此presum[hs]的逆需要乘在前面，才能把presum[hs]抵消掉

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
const ll mod=1e9+7;
const int n=2;//转换矩阵的尺寸为2*2 

ll qsm(ll a,ll b){//快速幂
    ll t=a,ans=1;
    while(b){
        if(b&1)    ans=ans*t%mod;
        t=t*t%mod;
        b>>=1;
    }
    return ans%mod;
}
ll ni(int x){//求逆元
    return qsm((ll)x,mod-2);
}

struct Matrix{
    static const int N=10;
    ll a[N][N];
    Matrix(ll e=0){//新建一个matrix变量时，自动初始化为全0矩阵
        for (int i=0;i<=n-1;i++)for (int j=0;j<=n-1;j++)a[i][j]=e*(i==j);
    }
    Matrix(ll a1,ll a2,ll a3,ll a4){
        a[0][0]=a1;    a[0][1]=a2;
        a[1][0]=a3;    a[1][1]=a4;
    }
}presum[100010];//当需要求矩阵的逆时，其尺寸为[n][n<<1] 
Matrix mul(Matrix A,Matrix B){
    Matrix ans(0);//构造全0矩阵 
    for (int i=0;i<=n-1;i++){
        for (int j=0;j<=n-1;j++){
            for (int k=0;k<=n-1;k++){
                ans.a[i][j]=(ans.a[i][j]+A.a[i][k]*B.a[k][j])%mod;
            }
        }
    }
    return ans;
}
Matrix ksm(Matrix A,ll b){
    Matrix ans(1);//构造单位阵 
    while (b){
        if (b&1)ans=mul(ans,A);
        A=mul(A,A);b>>=1;
    }
    return ans;
}
void row_minus(Matrix &A,int a,int b,ll k){//矩阵A的第a行减k*第b行 
    _for(i,0,2*n-1){
        A.a[a][i]=(A.a[a][i]-A.a[b][i]*k%mod+mod)%mod;
    }
}
void row_multiplies(Matrix &A,int a,ll k){//第a行乘k 
    _for(i,0,2*n-1){
        A.a[a][i]=(A.a[a][i]*k)%mod;
    }
}
void row_swap(Matrix &A,int a,int b){//交换a和b两行 
    _for(i,0,2*n-1){
        swap(A.a[a][i], A.a[b][i]);
    }
}
Matrix getinv(Matrix x){//求矩阵x的逆 
    Matrix A(0);
    _for(i,0,n-1){
        _for(j,0,n-1){
            A.a[i][j]=x.a[i][j];
            A.a[i][n+j]=(i==j);
        }
    }
    _for(i,0,n-1){
        if(!A.a[i][i]){
            _for(j,i+1,n-1){
                if(A.a[j][i]){
                    row_swap(A,i, j);
                    break;
                }
            }
        }
        row_multiplies(A,i,ni(A.a[i][i]));
        _for(j,i+1,n-1){
            row_minus(A,j, i, A.a[j][i]);
        }
    }
    _rep(i,n-1,0){
        _rep(j,i-1,0){
            row_minus(A,j, i, A.a[j][i]);
        }
    }
    Matrix ret(0);
    _for(i,0,n-1){
        _for(j,0,n-1){
            ret.a[i][j]=A.a[i][n+j];
        }
    }
    return ret;
}
const Matrix tA(1,1,0,1);
const Matrix tB(1,0,1,1);
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int h,q;
    cin >> h >> q;
    //presum[0]=Matrix(1,0,0,1); 
    presum[1]=Matrix(1,0,0,1); 
    Matrix ans=getinv(presum[0]);
    _for(i,2,h){
        char c;
        cin >> c;
        if(c=='/'){
            presum[i]=mul(presum[i-1],tA);
        }
        else if(c=='\\'){//注意打两个右斜杠 
            presum[i]=mul(presum[i-1],tB);
        }
    }
    while(q--){
        int hs,ht,ps,pt;
        cin >> hs >> ht >> ps >> pt;
        Matrix ans=mul(getinv(presum[hs]),presum[ht]);//注意顺序不可颠倒 
        cout << ans.a[ps][pt] << "\n";
    }
    return 0; 
}