题解：AT_abc436_g [ABC436G] Linear Inequation

· · 题解

前言

这一篇题解不需要多项式科技，只需要会背包问题。

复杂度 O(n^2A\log{m})，A=100 为物品价值值域。

做法原出处：一大佬的记录。

题目传送门，可能的有关题目。

分析

如果 m 很小，容易得到一个 O(nm) 的完全背包。

然而，m 很大，但是可以发现 A=100 很小。

考虑一个事实：完全背包问题可以看作是多重背包的一种特化，是每种物品充分多的多重背包。

不妨将问题转化为多重背包，多重背包有一个经典的优化：二进制优化。如此，可以将问题转化为 01 背包。

此处如果算出每个物品使用的上界再拆分未免繁琐，且不好利用，

考虑二进制优化原理：保证每一种原有的选择方案都可以对应一种新的选择方案。

可以考虑把多重背包拆出的最后一项补至 2^k，更简洁地，每个物品 i 拆分为 \log{m} 个，重量分别为 2^j\times A_i。

然而，我们还是没有解决背包过大的问题，可以考虑使用有关题目中的背包压缩技术。

如果我们将 2^0\times A_i 形式的物品全部统计了，那么以后将不会有重量为奇数的物品。

则转移方向将从一张 DAG 分为两个 DAG，此时可以压缩背包，将这两个 DAG 合并。

具体地，如果当前的 m 为奇数，那么 2k,2k+1 位（位指已经放入的重量）可以合并至 k；为偶数，则 2k-1,2k 位可以合并至 k。然后 m 减半（下取整）。

具体的推导可以从余量上考虑，比如 m=7 时，在后续的重量都是 2 的倍数的情况下，0,1 位能放的情况是相同的，故可以合并。

实现

事实上，可以不用显式地写出多重背包的二进制优化，因为在背包压缩后，物品的重量也要减半，具体实现可参考代码。

每次 01 背包的复杂度为 O(n\sum_iA_i)=O(n^2A)（背包的大小为 O(nA) 以确保每种物品都能放入），共 \log{m} 次，时间复杂度 O(n^2A\log{m})。

空间复杂度 O(nA\log{m})，应容易优化至 O(nA)。

:::info[code]

#include<bits/stdc++.h>
using namespace std;
#define mod 998244353

int n,A[105],dp[65][20005];
unsigned long long m;

inline void inc(int &a,int b){a+=b,(a>=mod)&&(a-=mod);}

int main(){
    scanf("%d%llu",&n,&m),dp[0][0]=1;
    for(int i=1;i<=n;i++) scanf("%d",&A[i]);
    for(int i=0;i<=60;i++,m>>=1){
        for(int j=1;j<=n;j++){
            for(int k=20001;k>=A[j];k--) inc(dp[i][k],dp[i][k-A[j]]);
        }
        for(int j=(m&1);j<=20001;j+=2){
            inc(dp[i+1][j>>1],dp[i][j]);
            if(j) inc(dp[i+1][j>>1],dp[i][j-1]);
        }
    }//算到 20001 的原因：m&1=1 时，需要统计 dp[][20000] 只能通过 20001 计算
    printf("%d",dp[61][0]);
    return 0;
}

:::