Codeforces 2035D题模块化减法问题排查请求

我正在做Codeforces的2035D题，已经理清了解题逻辑和实现思路，但代码在测试点3运行失败。我怀疑是模块化减法函数modSub出了问题，但找不到具体错误原因。

我的代码 #

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef long long ll;
const ll MOD = 1e9 + 7; // 补充原代码未显式声明的MOD常量

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; // 加mod保证结果非负
}

// 模块化乘法
ll modMul(ll a, ll b, ll mod) {
    return (1LL * (a % mod) * (b % mod)) % mod; // 1LL避免大数溢出
}

// 快速幂（模块化指数运算）
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;

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

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

        while (!pq.empty() && pq.top().first <= v[i]) {
            ll val = pq.top().first;
            cnt += pq.top().second;
            // 原代码中减1操作未做模块化处理，此处修正
            val = modMul(val, modSub(modExp(2, pq.top().second, MOD), 1, MOD), MOD);

            sum = modSub(sum, val, MOD);

            // 用快速幂替代循环乘2，提升效率并避免累积误差
            v[i] = modMul(v[i], modExp(2, pq.top().second, MOD), MOD);
            
            pq.pop();
        }

        sum = modAdd(sum, v[i], MOD);
        pq.push({sa, cnt});

        cout << sum << " ";
    }

    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

解题思路 #

• sa：将当前数组元素反复除以2，直到得到一个不含因子2的奇数；
• cnt：统计当前元素能被2整除的次数；
• 使用优先队列维护(sa, cnt)对，当当前元素大于等于队列顶部的sa时，将当前元素乘以2^cnt来最大化总和，同时更新全局总和sum。

问题疑点 #

我初步怀疑modSub函数存在错误，但不确定具体原因。另外，原代码中存在几处可能的问题：

1. 未显式定义MOD常量，可能导致编译或运行错误；
2. 计算modExp(2, pq.top().second, MOD)-1时，减1操作未做模块化处理，可能出现负数；
3. 循环乘2的操作效率低下，且多次模块化乘法可能累积误差，改用快速幂更可靠。

内容的提问来源于stack exchange，提问作者Parag Patkulkar