专题班前缀和练习题 - 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; }