专题班前缀和练习题 - E - 智乃酱的双塔问题

为什么是DP？
设 dp[i][0] 是左边第 i 层的方案数
dp[i][1] 是右边第 i 层的方案数
如果，左右侧之间是符号 /
那么，dp[i][1] = dp[i-1][0] + dp[i-1][1]，意思是，右边的第 i 层可以通过左边第 i-1 层和右边第 i-1 层上来
dp[i][0] = dp[i-1][0]
同理，左右侧之间是符号
那么，dp[i][0] = dp[i-1][0] + dp[i-1][1]
dp[i][1] = dp[i-1][1]
可见，第 i 层的状态可以由第 i-1 层的状态得到
为什么是矩阵？由 DP 可以得到矩阵。因为，上面的写法，就是矩阵乘法的形式
层数的一层一层移动，在数学原理上，可以转移为矩阵的一次一次乘法
前缀和是从哪里来的？
是从 hs 层移动到 ht 层。由于算到了 ht 层之后，得到了答案，没法根据 dp，去排除前面 1 ~ (hs-1) 层的影响。但是，矩阵是可以的
除以一个 A 矩阵，相当于乘以 A 矩阵的逆矩阵。
剩下的就是 zngg 的模板

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MAX_MAT = 2;
const ll mod = 1e9 + 7;

struct Mat{
    ll a[MAX_MAT][MAX_MAT];
    Mat(){
        for(int i = 0; i < MAX_MAT; i++){
            for(int j = 0; j < MAX_MAT; j++)
                a[i][j] = 0;
            a[i][i] = 1;
        }
    }
    Mat(ll a1, ll a2, ll a3, ll a4){
        a[0][0] = a1;
        a[0][1] = a2;
        a[1][0] = a3;
        a[1][1] = a4;
    }
};

ll quickpow(ll x, ll y, ll MOD){
    ll ans = 1;
    while(y){
        if (y & 1)
            ans = (x * ans) % MOD;
        x = (x * x) % MOD;
        y >>= 1;
    }
    return ans;
}

ll A[MAX_MAT][MAX_MAT << 1];
ll get_inv(ll x){
    return quickpow(x, mod - 2, mod);
} 

void row_minus(int a, int b, ll k){
    for(int i = 0; i < 2 * MAX_MAT; i++)
        A[a][i] = (A[a][i] - A[b][i] * k % mod) % mod, A[a][i] = (A[a][i] + mod) % mod;
}

void row_multiplies(int a, ll k){
    for(int i = 0; i < 2 * MAX_MAT; i++)
        A[a][i] = (A[a][i] * k) % mod;
}

void row_swap(int a, int b){
    for(int i = 0; i < 2 * MAX_MAT; i++)
        swap(A[a][i], A[b][i]);
}

Mat getinv(Mat x){
    memset(A, 0, sizeof(A));
    for(int i = 0; i < MAX_MAT; i++)
        for(int j = 0; j < MAX_MAT; j++)
            A[i][j] = x.a[i][j], A[i][MAX_MAT + j] = (i == j);
    for(int i = 0; i < MAX_MAT; i++){
        if (!A[i][i]){
            for(int j = i + 1; j < MAX_MAT; j++)
                if (A[j][i]){
                    row_swap(i, j);
                    break;
                }
        }
        row_multiplies(i, get_inv(A[i][i]));
        for(int j = i + 1; j < MAX_MAT; j++)
            row_minus(j, i, A[j][i]);
    }
    for(int i = MAX_MAT - 1; i >= 0; i--)
        for(int j = i - 1; j >= 0; j--)
            row_minus(j, i, A[j][i]);
    Mat ret;
    for(int i = 0; i < MAX_MAT; i++)
        for(int j = 0; j < MAX_MAT; j++)
            ret.a[i][j] = A[i][MAX_MAT + j];
    return ret;
}

const int MAXN = 1e5 + 10;
const Mat tA(1, 1, 0, 1);
const Mat tB(1, 0, 1, 1);
Mat operator * (Mat x, Mat y){
    Mat c;
    for(int i = 0; i < MAX_MAT; i++)
        for(int j = 0; j < MAX_MAT; j++)
            c.a[i][j] = 0;
    for(int i = 0; i < MAX_MAT; i++)
        for(int j = 0; j < MAX_MAT; j++)
            for(int k = 0; k < MAX_MAT; k++)
                c.a[i][j] = (c.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;
    return c;
}

Mat presum[MAXN];
char s[MAXN];
int n, m, hs, ht, ps, pt;

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    scanf("%s",s + 1);
    presum[0] = Mat(1, 0, 0, 1);
    for(int i = 1; i < n; i++)
        if (s[i] == '/')
            presum[i] = presum[i - 1] * tA;
        else
            presum[i] = presum[i - 1] * tB;
    while(m--){
        scanf("%d%d%d%d", &hs, &ht, &ps, &pt);
        Mat ans = getinv(presum[hs - 1]) * presum[ht - 1];
        printf("%lld\n", ans.a[ps][pt]);
    }
    return 0;
}