526互联

2023 Hubei Provincial Collegiate Programming Contest

发布时间 2023-05-01 10:49:38作者: Kidding_Ma

链接：https://codeforces.com/gym/104337

C

画个图看看，复杂度 \(O(1)\)。

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

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    cout << min(n, m) + (abs(n - m) + 1) / 2 << '\n';
    
    return 0;
}

F

\(\text{manacher}\) 会在字符串两端和中间加字符，所以只看奇数位就行，\(a_{i}=1\) 就 \(\text{a}\) 变 \(\text{b}\)，\(\text{b}\) 变 \(\text{a}\)，复杂度 \(O(n)\)。

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

using namespace std;
using i64 = long long;

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

    vector<int> a(2 * n + 2);
    for (int i = 0; i < 2 * n + 2; i++) {
        cin >> a[i];
    }

    char c[] = {'a', 'b'};
    string s = "a";
    int j = 0;

    for (int i = 3; i < 2 * n; i += 2) {
        if (a[i] == 1) {
            s += c[j ^= 1];
        } else {
            s += c[j];
        }
    }
    cout << s << '\n';
    
    return 0;
}

H

先考虑朴素，但是发现 \(deg_{i}\) 只有 \(\sqrt{2m}\) 种，复杂度 \(O(2m)\)。

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

using namespace std;
using i64 = long long;

constexpr int P = 998244353;

struct mint {
    i64 x;
    mint(const i64 &x) : x(x % P) {}
};

mint operator*(const mint &a, const mint &b) {
    return a.x * b.x;
}

mint operator+(const mint &a, const mint &b) {
    return a.x + b.x;
}

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

    vector<int> deg(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        u--, v--;
        deg[u]++;
        deg[v]++;
    }

    int mx = *max_element(deg.begin(), deg.end());

    vector<int> cnt(mx + 1);

    vector<int> f;
    for (int i = 0; i < n; i++) {
        if (!cnt[deg[i]]) {
            f.push_back(deg[i]);
        }
        cnt[deg[i]]++;
    }

    mint ans = 0;
    int N = f.size();
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            mint a = f[i] ^ f[j];
            mint b = f[i] & f[j];
            mint c = f[i] | f[j];
            mint k = 1LL * cnt[f[i]] * cnt[f[j]];
            ans = ans + a * b * c * k;
        }
    }
    cout << ans.x << '\n';

    return 0;
}

I

记 \(m=lcm(a_{1}, a_{2}, \cdots, a_{n})\)，题意抽象为，找最小的 \(t\)，使得 \(t(t +1)\) 为 \(2m\) 的倍数，用 \(\text{pollard rho}\) 对 \(m\) 质因子分解一下，\(t\) 和 \(t+1\) 互质，所以每种质因子的积只能其中一个的因子，直接枚举得到 \(a,b\)，可以子集枚举，也可以 \(\text{dfs}\)，最后问题转化为找 \(x,y\) 满足 \(by-ax=1\)，\(\text{exgcd}\) 搞一下，复杂度不会算。

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

using namespace std;
using i64 = long long;
using i128 = __int128;
 
i64 power(i64 a, i64 b, i64 m) {
    i64 res = 1;
    for (; b; b >>= 1, a = i128(a) * a % m) {
        if (b & 1) {
            res = i128(res) * a % m;
        }
    }
    return res;
}
 
bool isprime(i64 p) {
    if (p < 2) {
        return 0;
    }
    i64 d = p - 1, r = 0;
    while (!(d & 1)) {
        r++;
        d >>= 1;
    }
    int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    for (auto a : prime) {
        if (p == a) {
            return true;
        }
        i64 x = power(a, d, p);
        if (x == 1 || x == p - 1) {
            continue;
        }
        for (int i = 0; i < r - 1; i++) {
            x = i128(x) * x % p;
            if (x == p - 1) {
                break;
            }
        }
        if (x != p - 1) {
            return false;
        }
    }
    return true;
}
 
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
 
i64 pollard_rho(i64 x) {
    i64 s = 0, t = 0;
    i64 c = i64(rng()) % (x - 1) + 1;
    i64 val = 1;
    for (int goal = 1; ; goal <<= 1, s = t, val = 1) {
        for (int step = 1; step <= goal; step++) {
            t = (i128(t) * t + c) % x;
            val = i128(val) * abs(t - s) % x;
            if (step % 127 == 0) {
                i64 g = gcd(val, x);
                if (g > 1) {
                    return g;
                }
            }
        }
        i64 g = gcd(val, x);
        if (g > 1) {
            return g;
        }
    }
}

unordered_map<i64, int> getprimes(i64 x) {
    unordered_map<i64, int> p;
    function<void(i64)> get = [&](i64 x) {
        if (x < 2) {
            return;
        }
        if (isprime(x)) {
            p[x]++;
            return;
        }
        i64 mx = pollard_rho(x);
        get(x / mx);
        get(mx);
    };
    get(x);
    return p;
}

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (!b) {
    	x = 1;
    	y = 0;
    	return a;
    }
    i64 d = exgcd(b, a % b, x, y);
    i64 t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
}

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

    int n;
    cin >> n;
    vector<int> a(n);
    i64 m = 1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        m = lcm(m, a[i]);
    }

    m = 2 * m;

    auto p = getprimes(m);

    vector<i64> f;
    for (auto &[u, v] : p) {
        i64 res = 1;
        for (int i = 0; i < v; i++) {
            res *= u;
        }
        f.push_back(res);
    }

    int N = f.size();
    i64 ans = 9E18;

    function<void(int, i64)> dfs = [&](int j, i64 a) {
        if (j == N) {
            i64 b = m / a;
            i64 x = 0, y = 0;
            i64 g = exgcd(a, b, x, y);
            x = ((-x) % b + b) % b;
            if (x == 0) {
                x = b;
            }
            ans = min(ans, a * x);
            return;
        }
        dfs(j + 1, a);
        dfs(j + 1, a * f[j]);
    };

    dfs(0, 1);

    cout << ans << '\n';

    return 0;
}

J

前缀和，模拟一下，复杂度 \(O(n)\)。

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

using namespace std;
using i64 = long long;

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

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

    vector<i64> sum(a.begin(), a.end());
    partial_sum(sum.begin(), sum.end(), sum.begin());

    if (sum[n - 1] < 0) {
        cout << -1 << '\n';
        return 0;
    }

    i64 ans = 0;
    i64 cur = 0;
    i64 mx = 0;
    for (int i = 0; i < n; i++) {
        cur += sum[i];
        if (cur < 0) {
            if (mx == 0) {
                cout << -1 << '\n';
                return 0;
            }
            i64 k = (-cur + mx - 1) / mx;
            ans += k;
            cur += k * mx;
        }

        mx = max(mx, sum[i]);
        ans++;
    }
    cout << ans << '\n';

    return 0;
}

K

投出 \(i\) 输的概率为 \((\frac{m-i}{m-1})^{n}\)。

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

using namespace std;
using i64 = long long;

constexpr int P = 998244353;

i64 power(i64 a, i64 b) {
    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);
}

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

    i64 Inv = inv(power(m - 1, n));
    for (int i = 1; i <= m; i++) {
        cout << power(m - i, n) * Inv % P << " \n"[i == m];
    }

    return 0;
}

M

枚举那个 \(\text{1000}\) 块的，复杂度 \(O(x)\)。

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

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int x, y;
    cin >> x >> y;

    int N = 1E6;

    for (int i = 0; i <= x; i++) {
        int c = y - (i * 1000);
        if (c % 2500 == 0) {
            int j = c / 2500;
            if (j <= x - i) {
                cout << x - i - j  << ' ' << i << ' ' << j << '\n';
                return 0;
            }
        }
    }
    cout << -1 << '\n';

    return 0;
}