背包

ABC436G - Linear Inequation

求 $\displaystyle\sum_{i=1}^N A_i x_i \le M$ 的非负整数解数量。$N\le100$，$A _ i\le100$，$M\le10 ^ {18}$。

完全背包是多重背包的特化，即每种物品充分多的多重背包。多重背包有经典的二进制优化。具体而言，每个物品 $i$ 拆分为 $\log M$ 个，重量分别为 $2^m A_i$。如此，问题化为 01 背包。

考虑背包压缩：如果我们将 $2^0 A_i$ 的物品全部统计了，那么以后将不会有重量为奇数的物品。因此，剩余容量 $2k,2k+1$ 的方案可以合并至 $k$，然后令 $M$ 减半。

const int V = std::ranges::fold_left(A, 0LL, std::plus());
std::vector<Z> f(2 * V + 1);
f[0] = 1;
while (M) {
    for (auto a : A) {
        auto nf = f;
        for (int i = 0; i + a <= 2 * V; i++) {
            nf[i + a] += f[i];
        }
        f = std::move(nf);
    }
    std::vector<Z> nf(2 * V + 1);
    for (int i = 0; i <= 2 * V; i++) {
        nf[M / 2 - floor(M - i, 2)] += f[i];
    }
    f = std::move(nf);
    M /= 2;
}
std::cout << f[0] << "\n";