思路

对于每个盒子 $j$ ，我们需要找到满足条件的非空子集 $\mathbb{S}$ 的数量。盒子的尺寸为 $(w_j, l_j, h_j)$ 。我们令 $W_j = \min(w_j, l_j)$ 和 $H_j = h_j$ 。条件可以重写为：

P3675.第3题-立方体的非空子集

1000ms

Difficulty: 6

所属公司 : 美团

算法与标签>动态规划

给定 $n$ 个 $Fibonacci$ 立方体，第 $i$ 个立方体的边长为 $f_i，f_i$ 为 $Fibonacci$ 数列的第 $i$ 项，其中 $Fibonacci$ 数列定义如下：

$f_1=1,f_2=2,f_i=f_{i-1}+f_{i-2}(i>2)$

现有 $m$ 个空盒子，第 $j$ 个盒子的尺寸为宽度 $w_j$ 、长度 $l_j$ 和高度 $h_j$ 。

我们定义一个非空子集 $\mathbb{S} ∈$ { $1,2,...,n$ } 的立方体可以被放入第 $j$ 个盒子，当且仅当该子集满足以下两条抽象规则

$\begin{array}{c}\max _{i \in \mathbb{S} } f_{i} \leqq \min \left(w_{j}, l_{j}\right) \\\sum_{i \in \mathbb{S} } f_{i} \leqq h_{j}\end{array}$

对于每个盒子，计算满足上述条件的非空子集 $\mathbb{S}$ 的总数。

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≦T≦10^3)$ 代表数据组数，每组测试数据描述如下：

第一行输入两个整数 $n,m(2≦n≦25;1≦m≦2×10^5)$

此后 $m$ 行，第 $j$ 行输入三个整数 $w_j,l_j,h_j(1≦w_j,l_j,h_j≦10^4)$ ，代表第 $j$ 个盒子的尺寸。

除此之外，保证单个测试文件的 $m$ 之和不超过 $2×10^5$ 。

对于每一组测试数据，新起一行输出 $m$ 个整数，其中第 $j$ 个整数表示在第 $j$ 个盒子中满足条件的非空子集数目。

在几乎全部的情况下， $PyPy$ 的运行速度优于 $Python$ ，如果使用 $python$ 作答，我们建议您选择对应版本的 $PyPy$ 进行提交、而不是 $Python$ 。

输入

输出

7 1 3

输入

预期输出（选填）