思路

1. 问题分析与转化

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

1. $\max_{i \in \mathbb{S}} f_i \leq W_j$
2. $\sum_{i \in \mathbb{S}} f_i \leq H_j$

由于 $m$ 的值很大（最多 $2 \times 10^5$），而 $n$ 很小（最多 $25$），对每个盒子都遍历 $2^n - 1$ 个子集来检查条件是不可行的，会导致超时。这提示我们需要使用预计算的方法来加速查询。

问题的核心是将子集的两个属性（最大元素和元素和）与盒子的两个约束（$W_j, H_j$）进行匹配。我们可以对所有可能的子集进行分类。一个有效的分类方式是按照子集中最大元素的索引进行分组。

令 $k = \max_{i \in \mathbb{S}} i$。由于Fibonacci数列 $f_i$ 是递增的，所以 $\max_{i \in \mathbb{S}} f_i = f_k$。 此时，第一个条件变为 $f_k \leq W_j$。 这意味着，对于一个给定的盒子 $j$，任何可以放入的子集 $\mathbb{S}$，其最大元素的索引 $k$ 必须满足 $f_k \leq W_j$。

我们可以遍历所有可能的 $k$ (从 $1$ 到 $n$)，分别计算最大元素索引为 $k$ 的满足条件的子集数量，然后将它们加起来。 对于一个固定的 $k$，一个子集 $\mathbb{S}$ 的最大元素索引为 $k$，意味着 $k \in \mathbb{S}$，且 $\mathbb{S}$ 中的其他元素都来自集合 $\{1, 2, \ldots, k-1\}$。 这样的子集 $\mathbb{S}$ 可以表示为 $\{k\} \cup \mathbb{S}'$，其中 $\mathbb{S}' \subseteq \{1, 2, \ldots, k-1\}$。

现在，第二个条件 $\sum_{i \in \mathbb{S}} f_i \leq H_j$ 变为： $f_k + \sum_{i \in \mathbb{S}'} f_i \leq H_j$ $\sum_{i \in \mathbb{S}'} f_i \leq H_j - f_k$ 因此，对于一个给定的盒子 $j$ 和一个固定的 $k$（其中 $f_k \leq W_j$），我们需要计算的是：有多少个 $\{1, 2, \ldots, k-1\}$ 的子集 $\mathbb{S}'$，其元素对应的 $f_i$ 之和不大于 $H_j - f_k$。

2. 动态规划预计算

“一个集合的子集中，元素和不超过某個值的子集有多少个”，这是一个典型的动态规划（背包问题）可以解决的问题。 我们可以预计算出这些值。

定义一个二维DP数组 $\text{dp}[k][s]$，表示从前 $k-1$ 个Fibonacci数（即 $\{f_1, f_2, \ldots, f_{k-1}\}$）中选择任意个数，使得它们的和不大于 $s$ 的方案数。

DP状态转移方程推导如下： 考虑计算 $\text{dp}[k][s]$。子集是关于 $\{f_1, \ldots, f_{k-1}\}$ 的。这些子集可以分为两类：

1. 不包含 $f_{k-1}$ 的子集：这些子集实际上是 $\{f_1, \ldots, f_{k-2}\}$ 的子集。和不大于 $s$ 的方案数就是 $\text{dp}[k-1][s]$。
2. 包含 $f_{k-1}$ 的子集：这些子集的形式为 $\{f_{k-1}\} \cup \mathbb{S}''$，其中 $\mathbb{S}''$ 是 $\{f_1, \ldots, f_{k-2}\}$ 的子集。和的限制为 $f_{k-1} + \sum_{i \in \mathbb{S}''} f_i \leq s$，即 $\sum_{i \in \mathbb{S}''} f_i \leq s - f_{k-1}$。这样的方案数是 $\text{dp}[k-1][s - f_{k-1}]$。

综合起来，我们得到状态转移方程： $\text{dp}[k][s]$ = $\text{dp}[k-1][s]$ + $\text{dp}[k-1][s - f_{k-1}]$ (当 $s < f_{k-1}$ 时，第二项为0)

边界条件：$\text{dp}[1][s]$ 表示从空集 $\{\}$ 中选子集。只有空集这一个子集，其和为 $0$。所以对于任意 $s \geq 0$，$\text{dp}[1][s] = 1$。

注意到盒子的高度 $h_j$ 最大为 $10000$。因此，我们只需要计算 $s$ 在 $0$ 到 $10000$ 范围内的DP值。

C++

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 定义常量
const int MAXN = 25;
const int MAXH = 10001;

// f: Fibonacci数列
// dp[k][s]: 从前 k-1 个数中选择，和不超过 s 的方案数
long long f[MAXN + 2];
long long dp[MAXN + 2][MAXH];

// 预计算函数
void precompute(int n) {
    // 1. 计算Fibonacci数列
    f[1] = 1;
    f[2] = 2;
    for (int i = 3; i <= n; ++i) {
        // 防止溢出，虽然在此题n<=25不会
        if (f[i-1] + f[i-2] > 200000) {
            f[i] = 200001;
        } else {
            f[i] = f[i-1] + f[i-2];
        }
    }

    // 2. DP预计算
    // 边界条件：k=1, 从空集{}中选择，只有空集一种方案，和为0
    for (int s = 0; s < MAXH; ++s) {
        dp[1][s] = 1;
    }

    // 递推计算dp[k][s]
    for (int k = 2; k <= n; ++k) {
        for (int s = 0; s < MAXH; ++s) {
            // 方案1: 不选择 f[k-1]
            dp[k][s] = dp[k - 1][s];
            // 方案2: 选择 f[k-1]
            if (s >= f[k - 1]) {
                dp[k][s] += dp[k - 1][s - f[k - 1]];
            }
        }
    }
}

void solve() {
    int n, m;
    std::cin >> n >> m;

    // 每次测试数据都进行预计算
    precompute(n);

    std::vector<long long> results;
    for (int j = 0; j < m; ++j) {
        int w, l, h;
        std::cin >> w >> l >> h;

        int W = std::min(w, l);

        // 找到满足 f[k] <= W 的最大 k
        int k_max = 0;
        // 使用 upper_bound 可以在 O(log n) 时间内找到
        k_max = std::upper_bound(f + 1, f + n + 1, W) - f - 1;

        long long total_count = 0;
        // 遍历所有可能的子集最大元素索引 k
        for (int k = 1; k <= k_max; ++k) {
            int target_h = h - f[k];
            if (target_h >= 0) {
                // 累加方案数
                total_count += dp[k][target_h];
            }
        }
        results.push_back(total_count);
    }

    // 输出结果
    for (int i = 0; i < results.size(); ++i) {
        std::cout << results[i] << (i == results.size() - 1 ? "" : " ");
    }
    std::cout << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Python

import sys

# 定义常量
MAXN = 25
MAXH = 10001

# 全局变量用于存储预计算结果
f = [0] * (MAXN + 2)
dp = [[0] * MAXH for _ in range(MAXN + 2)]
precomputed_n = 0 # 标记已预计算的n，避免重复计算

def precompute(n):
    """
    预计算函数
    """
    global precomputed_n
    # 如果已经为相同的n或更大的n计算过，则跳过
    if precomputed_n >= n:
        return
    precomputed_n = n

    # 1. 计算Fibonacci数列
    f[1] = 1
    f[2] = 2
    for i in range(3, n + 1):
        f[i] = f[i-1] + f[i-2]

    # 2. DP预计算
    # 边界条件：k=1，从空集{}中选择，只有空集一种方案
    for s in range(MAXH):
        dp[1][s] = 1

    # 递推计算dp[k][s]
    for k in range(2, n + 1):
        for s in range(MAXH):
            # 方案1: 不选择 f[k-1]
            dp[k][s] = dp[k-1][s]
            # 方案2: 选择 f[k-1]
            if s >= f[k-1]:
                dp[k][s] += dp[k-1][s - f[k-1]]

def solve():
    """
    解决单个测试用例
    """
    n, m = map(int, sys.stdin.readline().split())
    
    # 预计算
    precompute(n)

    results = []
    for _ in range(m):
        w, l, h = map(int, sys.stdin.readline().split())
        
        W = min(w, l)
        
        # 找到满足 f[k] <= W 的最大 k
        k_max = 0
        for k in range(1, n + 1):
            if f[k] <= W:
                k_max = k
            else:
                break
        
        total_count = 0
        # 遍历所有可能的子集最大元素索引 k
        for k in range(1, k_max + 1):
            target_h = h - f[k]
            if target_h >= 0:
                # 累加方案数
                total_count += dp[k][target_h]
        
        results.append(total_count)

    # 输出结果
    print(' '.join(map(str, results)))


def main():
    """
    主函数
    """
    try:
        T_str = sys.stdin.readline()
        if not T_str: return
        T = int(T_str)
        for _ in range(T):
            solve()
    except (IOError, IndexError):
        return

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
    // 定义常量
    static final int MAXN = 25;
    static final int MAXH = 10001;

    // f: Fibonacci数列
    // dp[k][s]: 从前 k-1 个数中选择，和不超过 s 的方案数
    static long[] f = new long[MAXN + 2];
    static long[][] dp = new long[MAXN + 2][MAXH];

    // 标记是否已为某个n值计算过，用于优化
    static int precomputedN = 0;

    // 预计算函数
    public static void precompute(int n) {
        // 如果已经为相同的n或更大的n计算过，则跳过
        if (precomputedN >= n) {
            return;
        }
        precomputedN = n;

        // 1. 计算Fibonacci数列
        f[1] = 1;
        f[2] = 2;
        for (int i = 3; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }

        // 2. DP预计算
        // 边界条件：k=1，从空集{}中选择，只有空集一种方案
        Arrays.fill(dp[1], 1);

        // 递推计算dp[k][s]
        for (int k = 2; k <= n; k++) {
            for (int s = 0; s < MAXH; s++) {
                // 方案1: 不选择 f[k-1]
                dp[k][s] = dp[k - 1][s];
                // 方案2: 选择 f[k-1]
                if (s >= f[k - 1]) {
                    dp[k][s] += dp[k - 1][s - (int)f[k - 1]];
                }
            }
        }
    }

    public static void solve(FastReader sc, PrintWriter out) {
        int n = sc.nextInt();
        int m = sc.nextInt();

        // 预计算
        precompute(n);

        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < m; j++) {
            int w = sc.nextInt();
            int l = sc.nextInt();
            int h = sc.nextInt();

            int W = Math.min(w, l);

            // 找到满足 f[k] <= W 的最大 k
            int kMax = 0;
            // Java没有内置的upper_bound，线性扫描足够快
            for (int k = 1; k <= n; k++) {
                if (f[k] <= W) {
                    kMax = k;
                } else {
                    break;
                }
            }

            long totalCount = 0;
            // 遍历所有可能的子集最大元素索引 k
            for (int k = 1; k <= kMax; k++) {
                int targetH = h - (int)f[k];
                if (targetH >= 0) {
                    // 累加方案数
                    totalCount += dp[k][targetH];
                }
            }
            sb.append(totalCount).append(" ");
        }

        // 输出结果
        out.println(sb.toString().trim());
    }

    public static void main(String[] args) {
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        int T = sc.nextInt();
        while (T-- > 0) {
            solve(sc, out);
        }
        out.flush();
    }

    // 快速I/O模板
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

题目内容

给定 $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$ 。

样例1

输入

1
3 3
3 5 7
1 1 1
2 3 3

输出

7 1 3