列表

详情

NC223137. 智乃酱的双塔问题

描述

如图所示，在某个地方有两座层数为的高塔，两座高塔的内部各自都有连接到上一层的楼梯，即每座塔的第层可以直接上楼梯到第层。
同时，在两座高塔之间还会存在一些连接两座高塔的楼梯，具体来说，除了顶层以外，每一层都是以下这两种情况之一。
  1. 左侧高塔的第层有楼梯连接右侧高塔的第层。
  2. 右侧高塔的第层有楼梯连接左侧高塔的第层。
我们用字符'/'表示第1种情况，用字符'\'表示第二种情况。现在智乃想知道，她从某座高塔的第层移动到层（），在只能走楼梯上楼的情况下，有多少种不同的移动方案？
为了避免这个数字太大，你只用输出方案数对取余数后的结果即可。

输入描述

第一行输入两个正整数表示高塔的层数，以及询问的次数。
第二行输出一个长度大小为的字符串，字符串仅包括。
接下来行，每行四个整数，分别表示智乃酱一开始的层数，她想去的层数。
当为0时，表示一开始在左边的塔，否则表示一开始在右边的塔。
当为0时，表示她的终点为左边的塔，否则表示终点为右边的塔。

输出描述

输出行，每行一个正整数表示方案数对取余数后的结果。

示例1

输入: 

4 5
//\
1 4 0 0
2 4 0 0
2 4 0 1
3 4 0 1
3 4 1 0

输出: 

3
2
1
0
1

说明:

样例如题目描述中的图所示。
对于第一组查询：
从左边的塔第1层爬到左边的塔第4层共有3种方案：
1.直接在左侧塔内移动到第4层。
2.从左侧塔1层移动到右侧的塔2层，然后从右侧塔上楼移动到3层，最后从右侧塔3层移动到左侧塔4层。
3.先上楼，然后从左侧塔2层移动到右侧的塔3层，最后从右侧塔3层移动到左侧塔4层。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 55ms, 内存消耗: 7664K, 提交时间: 2022-02-18 17:49:40 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll N = 2e5 + 5;

struct Matrix {
	ll mat[2][2];
	Matrix() { memset(mat, 0, sizeof(mat)); }
	Matrix(ll a1, ll a2, ll a3, ll a4) {
		mat[0][0] = a1; mat[0][1] = a2;
		mat[1][0] = a3; mat[1][1] = a4;
	}
	Matrix inv() {
		return Matrix(mat[1][1],(mod -mat[0][1])%mod ,(mod - mat[1][0])%mod , mat[0][0]);
	}
	Matrix operator * (const Matrix &b) {
		Matrix c;
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				for (int k = 0; k < 2; k++)
					c.mat[i][j] = (c.mat[i][j] + mat[i][k] * b.mat[k][j] % mod) % mod;
		return c;
	}
} prefix[N];

ll n, m, hs, ht, ps, pt;
char c;

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	prefix[0] = Matrix(1, 0, 0, 1);
	for (int i = 1; i < n; i++) {
		cin >> c;
		if (c == '/') prefix[i] = prefix[i - 1] * Matrix(1, 1, 0, 1);
		else prefix[i] = prefix[i - 1] * Matrix(1, 0, 1, 1);
	}
	while (m--) {
		cin >> hs >> ht >> ps >> pt;
		cout << (prefix[hs - 1].inv() * prefix[ht - 1]).mat[ps][pt] << '\n';
	}
	return 0;
}

上一题

© 2025 nowcoder.com