题解 | # F. Knapsack #

$total$ $[思维+位运算+贪心]$

看似背包，实则一点也不背包，物品的数量为 $a_{i}$ ，每一个物品的体积是 $2^{b_{i} }$ ，所以体积一样的物品 $a_{i}$ 可以累加

然后一共有m个背包，求背包的最小体积，但可惜，也不是二分

正确的思路是从二进制和贪心的方向去想：

二进制上，考虑每一位的贡献，而不是将 $2_{b_{i}}$ 打开
二进制从大到小去想，1是因为如果先考虑小的体积，那么很有可能导致大的体积放不进去了，导致背包不充分填充；2是因为我们是考虑二进制每一位 $2^{b_{i} }$ ，如果当前 $2^{k}$ 有剩余，那么可以传递到下一位 $2\times 2^{k-1}$ ......

第一步：将二进制从大到小排序

bool cmp(pair<int, int> a, pair<int, int> b){
    return a.first > b.first;
}
int n, m; cin >> n >> m;    
map<int, int> ma;
for(int i = 1; i <= n; i ++){
    int a, b; cin >> a >> b;
    ma[b] += a;
}
vector<pair<int, int> > a;
for(auto [v, w] : ma) a.push_back({v, w});
sort(a.begin(), a.end(), cmp);

第二步：用 $total$ 记录当前可以使用的 $2^{b_{i}}$ 的个数， $pre$ 表示上一个 $2^{b_{i+1}}$ ，因为从 $2^{b_{i+1}}$ 到 $2^{b_{i}}$ 中间差了 $2^{b_{i+1}-b_{i}}$ ， $ans$ 记录答案

剪枝：在从大到小循环的过程中， $total$ 会不断的乘上 $2^{k}$ ，那么 $total$ 可能会超时 $long\ long$ 范围，思考：当当前的 $total$ 大于 $2^{50}$ 时，一定可以满足将后面的所有物品都装入背包中，所有剪枝：

$cnt$ 表示的是当前的 $total$ 的次方， $pre-v$ 的意思是 $2^{b_{i+1}}$ 到 $2^{b_{i}}$ 中间差了 $2^{b_{i+1}-b_{i}}$ ， $pre-v$ 就等于 $b_{i+1}-b_{i}$

if(total){
    int cnt = 0, now_total = total;
    while(now_total){
        cnt ++;
        now_total >>= 1;
    }
    if(cnt + pre - v > 50) break;
    total *= ksm(2, pre - v, 1000000000000000000);
}

然后如果当前的 $total$ 比 $w$ 大，那么就用掉 $w$ 个；否则，对于每一个背包，我需要添加容积为 $2^{v}$ 的个数是 $x=\frac{(w+m-1)}{m}$ ，所以 $ans$ 累加答案 $x\times 2^{v}$ ，然后 $total$ 为用剩下的空间： $x\times m- w$

if(w <= total) total -= w;
else{
    w -= total;
    int x = (w + m - 1) / m;
    ans = (ans + ((x % mod) * ksm(2, v, mod)) % mod) % mod;
    total = x * m - w;
}

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;

const int mod = 998244353;


bool cmp(pair<int, int> a, pair<int, int> b){
    return a.first > b.first;
}

int ksm(int a, int b, int p){
    int sum = 1;
    while(b){
        if(b & 1) sum = (sum * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return sum;
}

void solve(){

    int n, m; cin >> n >> m;
    map<int, int> ma;
    for(int i = 1; i <= n; i ++){
        int a, b; cin >> a >> b;
        ma[b] += a;
    }
    vector<pair<int, int> > a;
    for(auto [v, w] : ma) a.push_back({v, w});
    sort(a.begin(), a.end(), cmp);
    int total = 0, pre = a[0].first, ans = 0;

    for(int i = 0; i < (int)a.size(); i ++){
        int v = a[i].first, w = a[i].second;
        if(total){
            int cnt = 0, now_total = total;
            while(now_total){
                cnt ++;
                now_total >>= 1;
            }
            if(cnt + pre - v > 50) break;
            total *= ksm(2, pre - v, 1000000000000000000);
        }
        pre = v;
        if(w <= total) total -= w;
        else{
            w -= total;
            int x = (w + m - 1) / m;
            ans = (ans + ((x % mod) * ksm(2, v, mod)) % mod) % mod;
            total = x * m - w; 
        }
    }
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    cin >> tt;
    while(tt --) solve();
    return 0;
}