只能说是出题人完美解决了参赛队伍过多的问题

C. Optimal Strategy

#include <iostream>
#define rep(i, a, b) for(int i=a;i<=b;++i)
#define per(i, a, b) for(int i=a;i>=b;--i)
#define int long long
using namespace std;
const int N = 1e6 + 10, p = 998244353;
int n, a[N], t[N], s[N], fac[N], inv[N], ret = 1;
inline int ksm(int a, int b, const int &p)
{
    int c = 1;
    for (a %= p;b;a = a * a % p, b >>= 1) if (b & 1) c = c * a % p;
    return c;
}
inline void pre()
{
    fac[0] = inv[0] = 1;
    for (int i = 1;i < N;++i) fac[i] = fac[i - 1] * i % p;
    inv[N - 1] = ksm(fac[N - 1], p - 2, p);
    for (int i = N - 2;i > 0;--i) inv[i] = inv[i + 1] * (i + 1) % p;
}
inline int C(int n, int m) { return fac[n] * inv[m] % p * inv[n - m] % p; }
signed main()
{
    cin >> n; rep(i, 1, n) cin >> a[i], t[a[i]]++;
    rep(i, 1, n) s[i] = s[i - 1] + t[i]; pre();
    rep(i, 1, n) ret = ret * fac[t[i]] % p * C(s[i - 1] - s[0] + t[i] / 2, t[i] / 2) % p;
    return cout << ret, 0;
}

D. Arithmetic Sequence

#include <bits/stdc++.h>
#define rep(i, a, b) for(int32_t i=a;i<=b;++i)
#define per(i, a, b) for(int32_t i=a;i>=b;--i)
#define int long long
using namespace std;
const int N = 2e5 + 10, INF = 1e13;
int n, a[N], d[N], f[N], hf;
int check(int x)
{
    rep(i, 1, n) f[i] = f[i - 1] + x - d[i + 1];
    nth_element(f, f + hf, f + n);
    int ret = 0, mid = f[hf];
    rep(i, 1, n) ret += abs(mid - f[i - 1]);
    return ret;
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n; rep(i, 1, n) cin >> a[i], d[i] = a[i] - a[i - 1];
    int l = -INF, r = INF; hf = n / 2;
    if (n > 2e3) l /= n / 10, r /= n / 10; // 缩小三分值域
    while (l < r)
    {
        int midl = l + (r - l) / 3, midr = r - (r - l) / 3;
        if (check(midl) <= check(midr)) r = midr - 1;
        else l = midl + 1;
    }
    return cout << check(l), 0;
}

J. Determinant

#include <iostream>
#define rep(i, a, b) for(int i=a;i<=b;++i)
#define per(i, a, b) for(int i=a;i>=b;--i)
#define int long long
using namespace std;
const int N = 110, p = 1e9 + 7;
int n, a[N][N]; string s;
int gauss()
{
    int ret = 1, f = 1;
    rep(i, 1, n)
    {
        rep(j, i + 1, n)
        {
            while (a[i][i])
            {
                int div = a[j][i] / a[i][i];
                rep(k, i, n) a[j][k] = (a[j][k] - div * a[i][k] % p + p) % p;
                swap(a[i], a[j]), f = -f;
            }
            swap(a[i], a[j]), f = -f;
        }
    }
    rep(i, 1, n) ret = ret * a[i][i] % p;
    return (ret * f + p) % p;
}
void solve()
{
    cin >> n >> s; rep(i, 1, n) rep(j, 1, n) cin >> a[i][j];
    int ret = 0; for (auto &c : s) ret = (ret * 10 + c - '0') % p;
    cout << "-+"[ret == gauss()] << '\n';
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int _;for (cin >> _; _--;) solve();
    return 0;
}

K. Search For Mafuyu

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;++i)
#define per(i, a, b) for(int i=a;i>=b;--i)
#define int long long
using namespace std;
void solve()
{
    int n, u, v, cnt = 0; cin >> n; double ret = 0;
    vector<vector<int>> G(n + 1); vector<bool> vis(n + 1);
    rep(i, 2, n) cin >> u >> v, G[u].push_back(v), G[v].push_back(u);
    function<void(int, int)> dfs = [&](int x, int fa)
    {
        cnt++;
        if (!vis[x]) ret += cnt, vis[x] = 1;
        for (auto &i : G[x]) if (i != fa) dfs(i, x);
        cnt++;
    };
    dfs(1, 0), cout << (1.0 * (ret - 1) / (n - 1) - 1) << '\n';
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0); cout << fixed << setprecision(10);
    int _;for (cin >> _; _--; ) solve();
    return 0;
}