题解：超大容积完全背包问题（基于同余类优化）

一、题目核心分析

1. 问题本质

这是一道完全背包问题，但存在特殊约束：

• 物品可无限选，要求体积和恰好等于询问容积 (V)；
• 最大化价值和，若无解输出 (-1)；
• 关键难点：(V) 极大（(10^{11} \leq V \leq 10^{12})），传统动态规划（(O(Vn))）完全不可行。

2. 核心思路：同余类优化 + 贪心策略

（1）问题转化

由于 (V) 极大，需利用“同余类”将无限容积转化为有限状态：

• 选择一种“基准物品”（设其体积为 (v_{\text{base}})，价值为 (c_{\text{base}})），所有容积 (V) 可按模 (v_{\text{base}}) 分类，即 (V = k \cdot v_{\text{base}} + r)（(0 \leq r < v_{\text{base}})）；
• 对于每个余数 (r)，只需预处理出“体积和 ≡ (r \mod v_{\text{base}}) 且体积 ≤ (M)”（(M) 为某个有限值）的最大价值，后续可通过基准物品扩展到超大 (V)。

（2）基准物品选择

选择 单位体积价值最大 的物品作为基准物品：

• 单位体积价值 = (c_i / v_i)，排序后选择最优物品（代码中通过 Node 的 < 运算符按此规则排序）；
• 理由：基准物品是“性价比最高”的，当 (V) 极大时，最优解必然包含大量基准物品，仅需用其他物品填补余数部分。

（3）有限状态预处理

对每个余数 (r)（(0 \leq r < v_{\text{base}})），预处理 (f[r]) 表示：

• 体积和 ≡ (r \mod v_{\text{base}})；
• 体积 ≤ (2 \cdot v_{\text{base}})（保证能通过基准物品扩展）；
• 最大价值和。

（4）查询计算

对于询问 (V = k \cdot v_{\text{base}} + r)：

• 若 (f[r]) 无解（预处理时未更新），则输出 (-1)；
• 否则，最优解 = (k \cdot c_{\text{base}} + f[r])（(k) 个基准物品 + 余数 (r) 对应的最优组合）。

3. 关键证明

基准物品性价比最高，因此：

• 当体积足够大时，用基准物品填充剩余体积的价值最优；
• 预处理时只需覆盖“余数对应的最小体积组合”，后续可通过基准物品无限扩展（每增加一个基准物品，体积 + (v_{\text{base}})，价值 + (c_{\text{base}})）。

二、完整代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 2;  // 基准物品体积最大为1e5，故余数范围0~1e5-1
const ll mn = -1e13;       // 初始化价值为极小值（表示无解）

int n, q, v;               // v：基准物品体积
ll m, c, f[maxn];          // c：基准物品价值；f[r]：余数r的最大价值

// 物品结构体：按单位体积价值排序（c_i/v_i 降序）
struct Node {
    int v, c;
    // 比较规则：1ll * xy.c * zb.v > 1ll * zb.c * xy.v → xy的单位价值更高
    friend bool operator<(Node xy, Node zb) {
        return 1ll * xy.c * zb.v < 1ll * zb.c * xy.v;
    }
} b[58];  // n≤50，数组开58足够

bitset<maxn> vis;  // 标记余数是否已处理

// 辅助函数：更新x为max(x,y)
inline void G(ll &x, ll y) {
    if (x < y) x = y;
}

// 核心函数：处理余数s，用物品（体积t，价值w）更新同余类
inline void P(int s, int t, int w) {
    vis[s] = 1;  // 标记该余数已处理
    int next_r = (s + t) % v;  // 下一个余数
    ll next_val = f[s] + w - (s + t) / v * c;  // 转换为基准物品的价值等价形式
    G(f[next_r], next_val);

    // 遍历该物品能到达的所有余数（形成环）
    for (int i = next_r; i != s; i = (i + t) % v) {
        vis[i] = 1;
        int ni = (i + t) % v;
        ll nv = f[i] + w - (i + t) / v * c;
        G(f[ni], nv);
    }
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &b[i].v, &b[i].c);
    }

    // 1. 按单位体积价值降序排序，选择最后一个（性价比最高）作为基准物品
    sort(b + 1, b + n + 1);
    v = b[n].v;  // 基准体积
    c = b[n].c;  // 基准价值

    // 2. 初始化dp数组：f[r]表示余数r的最大价值，初始为极小值（无解）
    memset(f, -0x3f, sizeof f);
    f[0] = 0;  // 余数0（体积0）的价值为0

    // 3. 预处理所有非基准物品，更新同余类的最大价值
    for (int i = 1; i < n; i++) {
        vis.reset();  // 重置标记
        int t = b[i].v;  // 当前物品体积
        int w = b[i].c;  // 当前物品价值
        // 遍历所有余数，未处理过的则用当前物品更新
        for (int j = 0; j < v; j++) {
            if (!vis[j] && f[j] != -0x3f3f3f3f3f3f3f3f) {
                P(j, t, w);
                P(j, t, w);  // 两次调用，确保覆盖所有可能路径
            }
        }
    }

    // 4. 处理询问
    while (q--) {
        scanf("%lld", &m);  // 询问容积V = m
        int r = m % v;      // 计算余数r
        if (f[r] < mn) {    // f[r]仍为极小值，无解
            puts("-1");
        } else {
            // 最优价值 = (m//v)*基准价值 + 余数r的最大价值
            ll ans = (m / v) * c + f[r];
            printf("%lld\n", ans);
        }
    }

    return 0;
}

三、关键逻辑详解

1. 物品排序（基准物品选择）

• 结构体 Node 的 < 运算符定义：1ll * xy.c * zb.v < 1ll * zb.c * xy.v，等价于 xy.c/xy.v < zb.c/zb.v（交叉相乘避免浮点数误差）；
• 排序后，最后一个物品 b[n] 是单位体积价值最大的，作为基准物品。

2. 动态规划数组初始化

• f[r] 表示“体积和 ≡ (r \mod v) 且体积 ≤ (2v)”的最大价值；
• 初始值设为 (-0x3f3f3f3f3f3f3f3f)（极小值），表示无解；
• f[0] = 0：体积为 0 时价值为 0（初始状态）。

3. 同余类更新函数 P(s, t, w)

• 输入：当前余数 s、物品体积 t、物品价值 w；
• 功能：遍历该物品能到达的所有余数（形成环），更新每个余数的最大价值；
• 核心公式：next_val = f[s] + w - (s + t)/v * c：
  • 当添加一个体积为 t 的物品后，体积和为 s + k*v + t（k 为整数）；
  • 等价于“余数 (s+t)%v + (s+t)/v 个基准物品的体积”；
  • 为了统一用基准物品扩展，需减去 (s+t)/v 个基准物品的价值，后续查询时再补回。

4. 预处理过程

• 对每个非基准物品，遍历所有余数；
• 用 bitset 标记已处理的余数，避免重复计算；
• 两次调用 P(j, t, w)：确保覆盖“使用1个”和“使用2个”当前物品的情况，保证余数类的价值被充分更新。

5. 询问处理

• 对每个询问 (V = m)，计算余数 (r = m \mod v)；
• 若 f[r] 仍为极小值，说明没有体积和 ≡ (r \mod v) 的方案，输出 (-1)；
• 否则，最优解 = 基准物品的总价值（(m//v) 个） + 余数 (r) 对应的最大价值（f[r]）。

四、样例验证（输入样例）

样例输入

2 2
6 10  → 物品1：v=6，c=10（单位价值10/6≈1.666）
8 15  → 物品2：v=8，c=15（单位价值15/8=1.875）
100000000001
100000000002

预处理过程

1. 排序后，物品2（单位价值更高）作为基准物品：(v=8)，(c=15)；
2. 预处理物品1（(v=6)，(c=10)）：
   • 余数范围 (0 \sim 7)；
   • 对每个余数 (r)，计算“体积和 ≡ (r \mod 8)”的最大价值；
   • 例如，余数 (2)：可通过“3个物品1”（体积 (18 = 2 + 2*8)，价值 (30)），对应 f[2] = 30 - 2*15 = 0。

询问计算

1. 第一个询问 (V=100000000001)：

   • 余数 (r = 100000000001 \mod 8 = 1)；
   • f[1] 为极小值，无解，输出 (-1)。

2. 第二个询问 (V=100000000002)：

   • 余数 (r = 100000000002 \mod 8 = 2)；
   • f[2] = 0；
   • 基准物品数量 (k = 100000000002 // 8 = 12500000000)；
   • 总价值 = (12500000000 * 15 + 0 = 187500000000)（与样例输出一致）。

五、复杂度分析

1. 预处理复杂度

• 基准物品体积 (v_{\text{base}} \leq 1e5)；
• 非基准物品数量 (n-1 \leq 49)；
• 每个物品处理 (O(v_{\text{base}})) 个余数；
• 总预处理复杂度 (O((n-1) \cdot v_{\text{base}}) \leq 49 \times 1e5 = 4.9e6)，高效可行。

2. 查询复杂度

• 每个查询仅需 (O(1)) 计算余数和价值；
• (q \leq 1e5)，总查询复杂度 (O(q) = 1e5)，完全满足要求。

六、注意事项

1. 基准物品选择：必须选择单位体积价值最大的物品，否则扩展时无法保证最优性；
2. 大整数处理：使用 long long 避免价值溢出（(V \leq 1e12)，基准价值 (1e6)，总价值可达 (1e18)）；
3. 无解判断：初始 f 数组需设为足够小的极小值（如 (-1e13)），避免与合法价值混淆；
4. 同余类覆盖：预处理时需确保每个余数的价值被充分更新（两次调用 P 函数）。