← 返回题目列表

Codeforces · 2180/F2

F2. 控制车(困难版)

中文机器翻译题面 查看原题

这两个版本的限制不同,包括变量范围以及时间和内存限制。只有解决了这个问题的两个版本,你才能破解。请注意,困难版本的正确解决方案不一定是简单版本的有效解决方案。

我们有一个 控制车 的行为类似于随机变量。由于随机变量既不是真正随机的也不是真正可变的,所以我们的控制车既不是车也不是可控的!

无论如何,我们得到一个大小为 $$$n \times m$$$ 的网格,由 $$$n+1$$$ 水平线和 $$$m+1$$$ 垂直线的交点形成。网格包含 $$$(n+1)(m+1)$$$ 交叉点,它们是单元格周围的角。

An 方向 是将四个基本方向(上、下、左、右)之一分配给每个 $$$(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$$$ 为模。

示例

输入
复制

5
1 1
2 1
1 2
2 2
44 1000000000000000

输出
复制

40
1072
784
91072
179226577

注意

在第一个测试用例中,为了使方向有效,我们至少需要左下墙或右下墙之一来覆盖正方形的底部边框。我们还需要至少右上或右下墙之一来覆盖右边界。如果这两个条件都成立,则方向有效。

现在,如果右上角指向下方,左下角指向右侧,则左上角和右下角可以指向任意方向。因此,这种类型有 $$$16$$$ 有效方向。

第一种类型的有效方向示例。

如果右上角或左下角之一指向不同的方向,则右下角必须覆盖相应的边框。因此,只有其中之一可以指向不同的方向。总共有 $$$2 \cdot 3 \cdot 4 = 24$$$ 此类型的有效方向。

第二种类型的有效方向示例。

因此,最终答案是 $$$16 + 24 = 40$$$。

两个无效方向的示例。

链接到可视化工具