解决 CP 问题时的模减法问题

Question

我正在尝试解决这个 https://codeforces.com/problemset/problem/2035/D codeforces 问题。我理解逻辑和实现，但我想我的模算术失败了。这是我的代码：

ll modAdd(ll a, ll b, ll mod) {
    return (a % mod + b % mod) % mod;
}

ll modSub(ll a, ll b, ll mod) {
    return ((a - b)%mod + mod) % mod; // Adding mod ensures non-negative result
}

// Function for modular multiplication
ll modMul(ll a, ll b, ll mod) {
    return (1LL * (a % mod) * (b % mod)) % mod; // 1LL ensures no overflow for large numbers
}

// Function for modular exponentiation
ll modExp(ll base, ll exp, ll mod) {
    ll result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = modMul(result, base, mod);
        }
        base = modMul(base, base, mod);
        exp /= 2;
    }
    return result;
}

class Compare {
public:
    bool operator()(pair<ll, ll> below, pair<ll, ll> above)
    {
        return below.first > above.first;
    }
};

void solve() {
    ll n;
    cin>>n;

    vector<ll> v(n);
    for(ll i = 0; i<n; i++)cin>>v[i];

    priority_queue<pair<ll, ll>, vector<pair<ll,ll>>, Compare> pq;
    ll sum = 0;

    vector<ll> ans;
    for(ll i = 0; i<n; i++){
        
            ll sa = v[i];
            ll cnt = 0;

            while(sa % 2 == 0){
                sa = sa / 2;
                cnt++;
            }

            while(!pq.empty() && pq.top().first <= v[i]){
                
                
                ll val = pq.top().first;
                cnt+=pq.top().second;
                val = modMul(val, modExp(2, pq.top().second, MOD)-1, MOD);

                sum = modSub(sum, val, MOD);
                //sum = modAdd(pq.top().first, sum, MOD);

                for(ll j = 0; j<pq.top().second; j++){
                    v[i] = modMul(v[i], 2, MOD);
                }
                
                pq.pop();
            }
    
        
            sum =modAdd(v[i], sum, MOD);
            
            pq.push({sa , cnt});

    cout<<sum<<" ";    
    }

    cout<<endl;
}

说明：
变量 sa -> stripped 'a' 是通过将数组元素除以 2 直到不能除以 2 来获得的，这样它就没有因子 2。
变量 cnt -> 'a' 可以除以 2 的次数

将这两个作为一对保留优先级队列。
每当数组元素大于或等于 sa 时，我都会将该元素乘以 2^cnt，因为这样做会增加总和，通过这种方式，我将 2 的幂传播到相乘时将给出最大总和的元素与.

测试 3 失败， 我怀疑这是因为模减法，但不确定到底是什么导致了错误。

Answer 1

不用担心，找到问题所在了 这只是 while 循环中的比较

while(!pq.empty() && pq.top().first <= v[i])

这里，v[i]的值可以小于优先级队列的第一个值，因为对v[i]使用了mod，为了得到正确的答案，我需要将其与完整值进行比较而不对其进行修改

改成这样了

while(!pq.empty() && (cnt > 32 || pq.top().first <= sa*(1ll << cnt)))

它起作用了，尽管优先级队列给出了 TLE