Link

B

先排序，考虑枚举两个位置，计算这两个位置差的贡献。

∑i=0n−1∑j=0n−1∣ai−bj∣∑k=0min⁡(i,j)(ki)(kj)∑k=0min⁡(n−1−i,n−1−j)(kn−1−i)(kn−1−j)=∑i=0n−1∑j=0n−1∣ai−bj∣(min⁡(i,j)i+j)(min⁡(n−1−i,n−1−j)2n−2−i−j)\begin{aligned} &\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}|a_i-b_j|\sum_{k=0}^{\min(i,j)}(_{k}^{i})(_{k}^{j})\sum_{k=0}^{\min(n-1-i,n-1-j)}(_{k}^{n-1-i})(_{k}^{n-1-j})\\ =&\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}|a_i-b_j|(_{\min(i,j)}^{i+j})(_{\min(n-1-i,n-1-j)}^{2n-2-i-j}) \end{aligned}

O(n2)O(n^{2})。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int P = 998244353;
vector<i64> fac, ifac;

i64 power(i64 a, i64 b, int p = P) {
    i64 res = 1;
    for (; b; b >>= 1, a = a * a % p) {
        if (b & 1) {
            res = res * a % p;
        }
    }
    return res;
}
 
i64 inv(i64 x) {
    return power(x, P - 2);
}

void init(int N) {
    fac.assign(N + 1, 0);
    ifac.assign(N + 1, 0);
    fac[0] = 1;
    for (int i = 1; i <= N; i++) {
        fac[i] = fac[i - 1] * i % P;
    }
    ifac[N] = inv(fac[N]);
    for (int i = N - 1; i >= 0; i--) {
        ifac[i] = ifac[i + 1] * (i + 1) % P;
    }
}

i64 C(int n, int m) {
    if (m < 0 || m > n) {
        return 0;
    }
    return fac[n] * ifac[m] % P * ifac[n - m] % P;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
   
    init(4E3);
    
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x1 = i, y1 = j;
            int x2 = n - 1 - i, y2 = n - 1 - j;
            ans = (ans + abs(a[i] - b[j]) * C(x1 + y1, min(x1, y1)) % P * C(x2 + y2, min(x2, y2) % P)) % P;
        }
    }
    cout << ans << '\n';
                   
    return 0;
}

C

(n−1)!!×n!!=n!(n-1)!!\times n!!=n!。

nn 为偶数：1!!×2!!×3!!×…n!!=2!×4!×⋯×n!1!!\times 2!!\times 3!!\times \dots n!!=2!\times 4!\times \dots \times n!。

nn 为奇数：1!!×2!!×3!!×⋯×n!!=2!×4!×…(n−1)!×n!!1!!\times 2!!\times 3!!\times \dots \times n!!=2!\times 4!\times\dots (n-1)!\times n!!。

问题转化为求 n!n! 中因子 2,52,5 的个数，直接求 55 的个数就行，55 的个数肯定比较少。

即计算：(⌊251⌋+⌊451⌋+…⌊n51⌋)+(⌊252⌋+⌊452⌋+…⌊n52⌋)+⋯+(⌊25k⌋+⌊45k⌋+…⌊n5k⌋)(\lfloor\frac{2}{5^1}\rfloor+\lfloor\frac{4}{5^1}\rfloor+\dots \lfloor\frac{n}{5^1}\rfloor)+(\lfloor\frac{2}{5^2}\rfloor+\lfloor\frac{4}{5^2}\rfloor+\dots \lfloor\frac{n}{5^2}\rfloor)+\dots +(\lfloor\frac{2}{5^k}\rfloor+\lfloor\frac{4}{5^k}\rfloor+\dots \lfloor\frac{n}{5^k}\rfloor)

这个式子可以直接算。

nn 为奇数多算个 n!!n!!。

floor_sum(n, m, a, b)

It returns ∑i=0n−1⌊a×i+bm⌋\sum_{i = 0}^{n - 1} \left\lfloor \frac{a \times i + b}{m} \right\rfloor

O(log⁡m)O(\log m)

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
using i128 = __int128;

ostream &operator<<(ostream &os, const i128 &v) {
    if (v <= 1000000000000000000) {
        return os << i64(v);
    }
    return os << i64(v / 1000000000000000000) << setw(18) << setfill('0') << i64(v % 1000000000000000000);
}

i128 floor_sum(i128 n, i128 m, i128 a, i128 b) {
    i128 ans = 0;
    if (a < 0) {
        i128 a2 = (a % m + m) % m;
        ans -= n * (n - 1) / 2 * ((a2 - a) / m);
        a = a2;
    }
    if (b < 0) {
        i128 b2 = (b % m + m) % m;
        ans -= n * ((b2 - b) / m);
        b = b2;
    }
    while (1) {
        if (a >= m) {
            ans += n * (n - 1) / 2 * (a / m);
            a %= m;
        }
        if (b >= m) {
            ans += n * (b / m);
            b %= m;
        }
        i128 y_max = a * n + b;
        if (y_max < m) {
            break;
        }
        n = y_max / m;
        b = y_max % m;
        swap(m, a);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 n;
    cin >> n;

    i128 ans = 0;

    if (n % 2 == 1) {
        for (i64 p = 5; p <= n; p *= 5) {
            ans += (n / p + 1) / 2;
        }
        n--;
    }

    for (i64 p = 5; p <= n; p *= 5) {
        ans += floor_sum(n / 2, p, 2, 2);
    }
    cout << ans << '\n';

    return 0;
}

E

考虑从左到右扫，只要当前和为偶数就把它切开，这样就可以知道这个区间最多能分成多少个偶数部分。

前缀和，O(n+q)O(n+q)。

C++ Code 

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a[i] = x % 2;
    }

    vector<int> sum(n + 1);
    for (int i = 0; i < n; i++) {
        sum[i + 1] = sum[i] + a[i];
    }

    vector<array<int, 2>> cnt(n + 1);
    for (int i = 0; i < n; i++) {
        cnt[i + 1] = cnt[i];
        cnt[i + 1][sum[i + 1] % 2]++;
    }

    for (int i = 0; i < q; i++) {
        int l, r, k;
        cin >> l >> r >> k;

        l--;
        if ((sum[r] - sum[l]) % 2 == 0 && cnt[r][sum[r] % 2] - cnt[l][sum[l] % 2] >= k) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    
}

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

    return 0;
}

G

发现 zz 是 gcd⁡(x,y)\gcd(x,y) 倍数才有可能是 YES，又发现若 z=0z=0，除非 x,yx,y 有一个为 00 才 YES，因为限制操作 x≠yx\ne y。

O(log⁡max⁡(x,y))O(\log \max(x,y))

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int x, y, z;
    cin >> x >> y >> z;
    int g = gcd(x, y);
    if (x == z || y == z || (z != 0 && z % g == 0)) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

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

    return 0;
}