A16802 · Control Car (Hard Version)

题目描述

这两个版本的区别在于限制条件，包括变量的取值范围、时间和内存限制。仅当你同时解决了本题目的两个版本时，才可以进行 hack。请注意，困难版本的正确解未必是简单版本的有效解。 我们有一辆“控制小车”，它的行为类似于一个随机变量。正如随机变量既不是真正随机，也不是真正变量，我们的“控制小车”既不是汽车，也不可控！ 无论如何，给定一个 $n \times m$ 的网格，这个网格由 $n+1$ 条水平线和 $m+1$ 条竖直线交叉组成。网格包含 $(n+1)(m+1)$ 个交点，这些交点是单元格四周的角。 一种“朝向”是给每个交点分配一个四个基本方向（上、下、左、右）中的一个。因此，总共有 $4^{(n+1)(m+1)}$ 种可能的朝向方案。 对于一种朝向，请按如下流程操作： 1. 对于网格上的每个点，从该点按分配的方向画出一堵单位长度的墙。墙壁可能会重叠或伸出网格边界之外。 2. 将控制小车放在左上角的单元格 $(1,1)$。然后，只要小车没有停止，它就会按照这些规则移动： - 如果小车可以向下移动（即向下到达正下方单元格的路径没有被墙堵住），则它会因重力向下移动。 - 如果它不能向下移动但可以向右移动（即通向右侧相邻单元格的路径没有被墙堵住），则它会向右移动。 - 如果小车移动出网格或无法移动，则停止。 3. 如果控制小车最终停在网格内部，则该朝向方案是合法的。 请计算所有合法朝向的数量。由于答案可能非常大，请输出其对 $10^9+7$ 取模后的结果。

输入格式

每组测试数据包含多个测试用例。第一行为测试用例个数 $t$（$1 \le t \le 50$）。每个测试用例描述如下。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le \mathbf{50}$，$1 \le m \le \mathbf{10^{15}}$），表示网格的大小。 所有测试用例中 $n$ 的总和不超过 $\mathbf{50}$。

输出格式

对于每个测试用例，输出合法朝向的数量，对 $10^9+7$ 取模后的结果。

输入输出样例

输入 #1

5
1 1
2 1
1 2
2 2
44 1000000000000000

输出 #1

A16802 | Control Car (Hard Version)

题目描述

输入格式

输出格式

输入输出样例

A16802 | $Control Car (Hard Version)$