题解：P13349 「ZYZ 2025」自然数序列

· · 题解

P13349 完全背包题解

题意简述

给定长度为 n 的正整数序列 a，进行 q 次询问。每次询问给定 l, r, k 和 k 个限制条件，求满足 l \leq \sum_{i=1}^{n} a_i b_i \leq r 和所有限制条件的自然数序列 b 的数量。结果对 998244353 取模。

思路

一道背包 DP 题，核心是计算在 k 个位置固定的前提下，序列 b 的加权和落在 [l, r] 的方案数。我们可以 DP 预处理全局背包，再通过退背包处理 k 个限制条件，最后计算区间和。定义 g_s 为完全背包计算所有物品任意取值时，加权和为 s 的方案数，转移为 g_j=(g_j+g_{j-a_i}) \bmod 998244353，其中 a_i 为物品重量。

对于每个询问：

  1. 根据 k 个限制条件，累加固定位置的贡献 s = \sum a_x \cdot y。若 s > r，则直接输出 0。

  2. 自由部分需满足 [\max(0, l-s), r-s]，若区间无效则直接输出 0。

  3. 将固定位置对应的物品从全局背包中移除（按重量降序进行逆背包操作）。

  4. 最后，在 [\max(0, l-s), r-s] 区间内累加方案数。

具体详见代码注释。

特别注意

本题时限改为 500ms 后此代码有点卡常，开 O2、关同步流、endl 改 '\n' 之后多试两次能过（亲测）（数据最强的点跑到了 498ms，如果卡不过可以手写快读快写）。

Code

码风良好，放心食用！
#include <bits/stdc++.h>
using namespace std;

const int N = 5000;         // 背包最大值
const int MOD = 998244353;
int n, q;
int a[5005];
int g[5005];                // 全局背包数组

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    // 初始化全局背包：完全背包DP
    memset(g, 0, sizeof(g)); // 清空背包数组
    g[0] = 1;                // 加权和为 0 的方案数为 1（全取 0）
    for (int i = 0; i < n; i++) {
        int av = a[i];       // 当前物品重量
        // 完全背包状态转移
        for (int j = av; j <= N; j++) {
            g[j] = (g[j] + g[j - av]) % MOD; // 累加方案数
        }
    }
    // 处理每组询问
    while (q--) {
        long long l, r;      // 区间边界
        int k;               // 限制条件数量
        cin >> l >> r >> k;
        int fv[8];           // 存储固定物品的重量
        int fc = 0;          // 固定物品计数器
        long long s = 0;     // 固定部分的总贡献

        // 处理k个限制条件
        for (int i = 0; i < k; i++) {
            int x, y;
            cin >> x >> y;
            x--;             // 转换为0-indexed
            // 累加固定位置的贡献：a[x] * y
            s += (long long)a[x] * y;
            fv[fc++] = a[x]; // 存储物品重量
        }

        // 固定部分已超过r，无解
        if (s > r) {
            cout << 0 << '\n';
            continue;
        }

        // 计算自由部分需满足的区间[Lp, Rp]
        long long Lp = l - s;
        long long Rp = r - s;
        // 处理Lp下界（非负）
        if (Lp < 0) Lp = 0;
        // 区间无效的情况
        if (Rp < 0 || Lp > Rp) {
            cout << 0 << '\n';
            continue;
        }

        int h[N + 1];                   // 临时背包数组
        memcpy(h, g, sizeof(int) * (N + 1)); // 复制全局背包到临时数组
        sort(fv, fv + fc, greater<int>()); // 按重量降序排序（优化内存访问）

        // 退背包：移除固定物品
        for (int i = 0; i < fc; i++) {
            int av = fv[i]; // 当前物品重量
            // 逆序更新背包（完全背包逆操作）
            for (int j = N; j >= av; j--) {
                h[j] -= h[j - av];       // 移除当前物品的贡献
                if (h[j] < 0) h[j] += MOD; // 处理负数取模
            }
        }

        // 计算自由部分在[Lp, Rp]的方案数
        int ans = 0;
        // 遍历区间（注意j不超过N）
        for (int j = Lp; j <= Rp && j <= N; j++) {
            ans = (ans + h[j]) % MOD; // 累加方案数（可以加个前缀和优化，但是不加也勉强）
        }
        cout << ans << '\n';
    }
    return 0;
}