2025 ICPC 武汉 F

共计 2043 个字符，预计需要花费 6 分钟才能阅读完成。

通过观察，我们很容易发现应该将重量相同的物品分到一起，呢么每一种重量的物品的数量范围就会变成 $[0,2\times 10^{14}]$ ，我们从大到小放置物品，如果我么能放恰好平均放满每一个背包，呢就直接放，然后让我们的答案增加 $(qmi(2,vec[i].first) * num1) % MOD)$ , $num1$ 表示我们每一个背包放多少个该重量的物品，$vec[i].first$ 表示 $i$ 物品重量的指数位。

但倘若不能恰好放满，我们就会先让答案增加 $(qmi(2,vec[i].first) * (num1 + 1)) % MOD)$ ，$num1 + 1$ 是因为余出来的数一定会让最大值增加一倍当前重量。这样的情况下就会有 $m - vec[i].second % m$ 个位置空下来，这里我们就要去向重量次小的拿，倘若我们要需要拿的物品 $j$ 的数量已经超过了 $2^{14}$ 呢么显然是不可能的，这种情况下我们最好向前借的情况是 $2\times 10^{14} \times (\dfrac{1}{2} + \dfrac{1}{4} + \dfrac{1}{8} \dots) < 2\times 10^{14}$，一定无法全部拿到，直接返回当前答案。其他情况就一直往前借，直到全部拿到，或者全拿了一遍也拿不全。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define int long long
#define double long double
#define PII pair<int, int> 
#define all(vec) vec.begin(),vec.end()  
using namespace std;
const int N = 1e6+10 ;
const int M = 1e3+10 ;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 998244353 ;
const int MAX = 2e14 ;
const double eps = 1e-9 ;
int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); }
int lcm(int a, int b){ return a * b / gcd(a,b); } 
int qmi(int a, int b){
    int res = 1 ;
    while(b){
        if(b&1LL) res = a * res % MOD ;
        b >>= 1 ;
        a = a * a % MOD ;
    }
    return res ;
}
int qmi2(int a, int b){
    int res = 1 ;
    while(b){
        if(b&1) res = a * res  ;
        if(res > 1e9) return res ;
        b >>= 1 ;
        a = a * a  ;
    }
    return res ;
}
int _ = 1 ;
int ans = 0 ;
int n , m, k, q ;
void solve(){
    ans = 0 ;
    cin >> n >> m ;

    map<int,int> mp ;
    int a, b ;
    for(int i = 1; i <= n ; ++ i){
        cin >> a >> b ;
        mp[-b] += a ;
    }
    vector<PII> vec ;
    for(auto e : mp){
        vec.push_back({-e.first,e.second}) ;
    }
    for(int i = 0 ; i < (int)vec.size() ; ++ i){
        if((int)vec[i].second == 0LL) continue; 
        int j = i + 1 ;
        int num1 = (vec[i].second / m) % MOD ;
        if(vec[i].second % m == 0LL){
            ans = (ans + (qmi(2,vec[i].first) * num1) % MOD) % MOD ; 
            vec[i].second = 0 ;
        }else{
            ans =  (ans + (qmi(2,vec[i].first) * (num1 + 1)) % MOD) % MOD ;
            int num2 = m - vec[i].second % m ;
            int p = i ;
            bool f = false ;
            vec[i].second = 0 ;
            while(j < vec.size() ){//寻找比其小的数来补齐
                if( vec[p].first - vec[j].first >= 51  || num2 > MAX || num2  > MAX / (1LL << (2,vec[p].first - vec[j].first)) ){
                    cout << ans << endl ;
                    return ;
                }
                int num3 = num2 * (1LL << (2,vec[p].first - vec[j].first)) ;//需要 num3 个 j
                if(vec[j].second >= num3){//说明补齐了
                    vec[j].second -= num3 ;
                    num3 = 0 ;
                    f = true ;
                    break ; 
                }else{
                    p = j ;
                    num2 = num3 - vec[j].second ;
                    vec[j].second = 0 ;
                    j ++ ;
                }
            }
            if(!f){
                cout << ans << endl ;
                return ;
            }
        }
    }
    cout << ans << endl ;
}
signed main(){
    IOS ;
    cin >>_ ;
    while(_ --){
        solve() ;
    }
    return 0;

}