河南萌新联赛第（三）场，个人题解

A

解题思路：

考虑线段树维护如下信息：

• $su{m}_{1}sum\_1$ 表示区间 $[l,r][l,r]$ 中每个人目前的月工资的总和。

• $laz{y}_{1}lazy\_1$ 表示 $su{m}_{1}sum\_1$ 的懒标记。

• $su{m}_{2}sum\_2$ 表示区间 $[l,r][l,r]$ 中每个人目前所有 $qq$ 个月的工资总和。

  这里我们采用提前发放工资的想法，我直接维护每个人最后能获得的工资是多少。

• $laz{y}_{2}lazy\_2$ 表示 $su{m}_{2}sum\_2$ 的懒标记。

我们考虑第一个操作，我们发现给区间 $[l,r][l,r]$ 的工资上涨 $ww$。

首先相当于给区间中每个人的月工资都加上 $ww$。

那么我们再考虑对于区间中每个人目前所有 $qq$ 个月的工资总和应该怎么变。

由于我们工资上涨了，那么从当前月到后面的月份，我的工资都会多出 $ww$。

若当前是第 $ii$ 月，则我们发现区间中每个人 $qq$ 个月的总工资都会增加：$(q-i+1)\times w\mathrm{。}(q-i+1)\backslash times\; w。$。

那么现在我们需要询问 $[l,r][l,r]$ 中每个人前 $ii$ 个月的工资总和 $ansans$ 是多少。

不难得出： $ans=su{m}_2-(q-i)\times su{m}_{1}ans=sum\_2-(q-i)\backslash times\; sum\_1$。

意思是我们若到第 $ii$ 天我们的月工资总和是 $su{m}_{1}sum\_1$ ，那么接下来剩下的 $(q-i)(q-i)$ 个月我们每个月都会多出这 $su{m}_{1}sum\_1$，所以我们需要用总的 $qq$ 个月的工资减去这部分，即可得到前 $ii$ 个月的。

分析到此，就变成了维护两个信息，两个标记的区间加线段树板子题了。

Code

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

const int N = 2e5 + 10, mod = 998244353;
struct node {
    int l, r;
    LL s[2], lazy[2];
}tr[4 * N];

void pushup(int u) {
    tr[u].s[0] = (tr[u << 1].s[0] + tr[u << 1 | 1].s[0]) % mod;
    tr[u].s[1] = (tr[u << 1].s[1] + tr[u << 1 | 1].s[1]) % mod;   
}

void pushdown(int u, int t) {
    if (tr[u].lazy[t]) {
        tr[u << 1].s[t] += (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].lazy[t] % mod;
        tr[u << 1 | 1].s[t] += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].lazy[t] % mod;
        tr[u << 1].lazy[t] += tr[u].lazy[t];
        tr[u << 1 | 1].lazy[t] += tr[u].lazy[t];   
        tr[u << 1].s[t] %= mod;
        tr[u << 1 | 1].s[t] %= mod;
        tr[u << 1].lazy[t] %= mod;
        tr[u << 1 | 1].lazy[t] %= mod;
        tr[u].lazy[t] = 0;
    }
}

void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) return ;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, LL w, int t) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].lazy[t] = (tr[u].lazy[t] + w) % mod;
        tr[u].s[t] = (tr[u].s[t] + w * (tr[u]. r - tr[u].l + 1) % mod) % mod;
        return; 
    }
    pushdown(u, t);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid) modify(u << 1, l, r, w, t);
    if (r > mid) modify(u << 1 | 1, l, r, w, t);
    pushup(u);
}

LL query(int u, int l, int r, int t) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].s[t];
    pushdown(u, t);
    int mid = (tr[u].l + tr[u].r) >> 1;
    LL res = 0;
    if (l <= mid) res = (res + query(u << 1, l, r, t)) % mod;
    if (r > mid) res = (res + query(u << 1 | 1, l, r, t)) % mod;
    return res;
}

int main() {
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    build(1, 1, n);
    for(int i = 1; i <= q; i++) {
        int op;
        cin >> op;
        if (op == 0) {
            int l, r, w;
            cin >> l >> r >> w;
            modify(1, l, r, w % mod, 0);
            modify(1, l, r, (q - i + 1LL) * w % mod, 1);
        } else {
            int l, r;
            cin >> l >> r;
            LL s1 = query(1, l, r, 1);
            LL s2 = query(1, l, r, 0) * (q - i) % mod;
            cout << ((s1 - s2) % mod + mod) % mod << '\n';
        }
    }

    return 0;
}

C

解题思路

要求满足 $A\times B+C\times D=nA\backslash times\; B+C\backslash times\; D=n$ 的四元组 $(A,B,C,D)(A,B,C,D)$ 的数量，首先我们可以把 $A\times BA\backslash times\; B$ 和 $C\times DC\backslash times\; D$ 分别看成两个整体，

我们不妨设 $x=A\times Bx=A\backslash times\; B$，$y=C\times By=C\backslash times\; B$。

令 $f(x)f(x)$ 表示满足 $x=u\times vx=u\backslash times\; v$ 的二元组 $(u,v)(u,v)$ 的数量，那么我们可以枚举 $xx$ 的取值，那么自然 $y=n-xy=n-x$。

故我们得到了 $ans={\sum }_{x=1}^{n-1}f(x)\times f(n-x)ans=\backslash sum\_\{x=1\}^\{n\; -\; 1\}f(x)\backslash times\; f(n\; -\; x)$。

这样我们就把四元组问题，转成了二元组，现在我们重点讨论一下如何求解 $f(x)f(x)$。

若 $x=u\times vx=u\backslash times\; v$，那么我们可以知道 $u,vu,v$ 必须都是 $xx$ 的因子，那么记 $tottot$ 表示 $xx$ 的因子个数，那么 $f(x)=totf(x)=tot$

比如 $x=8x=8$，其因子为：$1,2,4,81,2,4,8$ ，个数为 $44$，那么一共就有 $44$ 种不同的二元组满足条件：$(1,8),(8,1),(2,4),(4,2)(1,8),(8,1),(2,4),(4,2)$。

据此问题转化为了求解 $xx$ 的因子个数，由于 $1\le n\le 10^{5}1\backslash leq\; n\backslash leq\; 10^5$ ，故我们可以采用如下两种方法求解： 方法1：试除法，复杂度是 $O(n\sqrt{n})O(n\backslash sqrt\; n)$

方法2：调和级数复杂度枚举 ，复杂度是 $O(nlogn)O(nlogn)$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef __int128 i128;

int main() {
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> f(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            f[j]++;
        }
    }
    LL ans = 0;
    for (int i = 1; i < n; i++) {
        ans += 1LL * f[i] * f[n - i];
    }
    cout << ans << '\n';

    return 0;
}

D

解题思路

• $x+y=sx+y=s$

对于此类问题，我们通常需要把数进行二进制展开，一位位看。

那么对于 $aa$ 的第 $ii$ 位，如果它是 $11$，那么就意味这 $xx$ 和 $yy$ 的第 $ii$ 位都要为 $11$。

给出一个等式：。

那么如果 ，一定是无解，因为 $x⨁yx\backslash bigoplus\; y$ 不可能弄出负数

否则记

我们继续看 $bb$ 的第 $ii$ 位，如果第 $ii$ 为是 $11$，且此时 $xx$ 和 $yy$ 的第 $ii$ 为都是 $11$，此时发生矛盾，因为这样

$x⨁yx\backslash bigoplus\; y$ 在第 $ii$ 位的结果一定是 $00$；那么如果 $bb$ 的第 $ii$ 位是 $00$，无论 $xx$ 和 $yy$ 这一位是否被确定，我们都可以构造一个合法的组合使得它成立。例如当 $bb$ 的第 $ii$ 位是 $00$，那么 $xx$ 和 $yy$ 的第 $ii$ 位可以是 $(1,1),(0,0)(1,1),(0,0)$；若当 $bb$ 的第 $ii$ 位是 $00$，那么 $xx$ 和 $yy$ 的第 $ii$ 位可以是 $(1,0),(0,1)(1,0),(0,1)$。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef __int128 i128;

void solve() {
    LL a, s;
    cin >> a >> s;
    if (s < (i128)2 * a) {
        cout << "No\n";
        return ;
    }
    vector<int> x(61, -1), y(61, -1);
    LL b = s - 2 * a; // x ^ y
    for (int i = 0; i <= 60; i++) {
        if (a >> i & 1) {
            x[i] = y[i] = 1;
        }
    }
    for (int i = 0; i <= 60; i++) {
        int u = b >> i & 1;
        if (x[i] == 1 && y[i] == 1 && u) {
            cout << "No\n";
            return ;
        }
    }
    cout << "Yes\n";
}

int main() {
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}