2026夏组队训练赛第十三场

C. Optimal Strategy

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <complex>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
void pr(vector<int> a) {
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';
}
const int mod = 998244353;
const int INF = 1e18;
const int N = 1e6 + 5;

int power(int n, int p) {
    int res = 1, base = n;
    while (p) {
        if (p & 1)
            res = res * base % mod;
        base = base * base % mod;
        p >>= 1;
    }
    return res;
}

int fac[N], inv[N];

void init() {
    int n = 1e6+4;
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv[n] = power(fac[n], mod - 2);
    for (int i = n - 1; i; --i) {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}

int C(int n, int m) {
    if (m < 0 || n < 0)
        return 0;
    if (m > n)
        return 0;
    return fac[n] * inv[n - m] % mod * inv[m] % mod;
}
void solve() {
    int n;
    cin>>n;
    vi a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    vi cnt(n+1);
    for(int i=0;i<n;i++)cnt[a[i]]++;
    int sum=0;
    int ans=1;
    for(int i=0;i<=n;i++){
        ans*=C(sum+cnt[i]/2,cnt[i]/2)*fac[cnt[i]]%mod;
        sum+=cnt[i];
        ans%=mod;        
    }
    cout<<ans<<endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    // cin>>t;
    while (t--) {
        solve();
    }
    return 0;
}

D. Arithmetic Sequence

关于公差和首项都是凸函数，其中首项的最优取值知道公差之后可以直接求出来，所以直接对 k 三分。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 200010;
LL a[N], b[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    LL l = -20000000000000LL, r = 20000000000000LL;

    auto check = [&](LL mid) -> __int128_t {
        for (int i = 1; i <= n; ++i) b[i] = a[i] - i * mid;
        nth_element(b + 1, b + (n + 1) / 2, b + n + 1);
        __int128_t res = 0;
        for (int i = 1; i <= n; ++i) {
            res += abs(b[i] - b[(n + 1) / 2]);
        }
        return res;
    };

    while (l + 100 < r) {
        LL lm = (l * 2 + r) / 3, rm = (l + r * 2) / 3;
        __int128_t lv = check(lm), rv = check(rm);
        if (lv <= rv) r = rm;
        else l = lm;
    }

    __int128_t res = (__int128_t)LLONG_MAX * n;
    for (LL i = l; i <= r; ++i) {
        res = min(res, check(i));
    }
    cout << (LL)res << '\n';
    return 0;
}

E. Insidemen

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <complex>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
void pr(vector<int> a) {
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';
}
const int mod = 998244353;
const int INF = 1e18;
const int N = 1e6 + 5;
void init() {}
struct BIT {
    vector<int> tr;
    int n;
 
    BIT(int n) : n(n) {
        tr.assign(n + 1, 0);
    }
 
    void add(int x, int v) {
        for (; x <= n; x += x & -x) tr[x] += v;
    }
 
    int query(int x) {
        int res = 0;
        for (; x; x -= x & -x) res += tr[x];
        return res;
    }
    int sum(int l, int r) {
        return query(r) - query(l - 1);
    }
};
void solve() {
    int n, m;
    cin >> n >> m;
    vpii a(m);
    vi cnt(n+1);
    vvi c(n+1,vi(n+1));
    vvi ps(n+1,vi(n+1));
    vvi t(n+1),t1(n+1);
    BIT tr(n+2),tr1(n+2);
    for (int i = 0; i < m; i++) {
        cin >> a[i].f >> a[i].s;
        if(a[i].s<a[i].f)swap(a[i].s,a[i].f);
        t[a[i].s].pb(a[i].f);
        t1[a[i].f].pb(a[i].s);
        ps[a[i].f][a[i].s]+=a[i].f+a[i].s;
        ps[a[i].s][a[i].f]+=a[i].f+a[i].s;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ps[i][j]+=ps[i][j-1];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(auto j:t[i]){
            int z=tr.sum(j,i)*(i+j);
            cnt[j]+=z;
            cnt[i]+=z;
            c[j][i]+=z;
            ans+=z;
        }
        for(auto j:t[i]){
            tr.add(j,-i-j);
            tr.add(i-1,i+j);
        }
    }
 
    for(int i=n;i>=1;i--){
        for(auto j:t1[i]){
            int z=tr1.sum(i,j)*(i+j);
            cnt[j]+=z;
            cnt[i]+=z;
            c[i][j]+=z;
            ans+=z;
        }
        for(auto j:t1[i]){
            tr1.add(j,-i-j);
            tr1.add(i+1,i+j);
        }
    }
    ans/=2;
    for(int x=1;x<=n;x++){
        for(auto [l,r]:a){
            if(x==l||x==r)continue;
            int s=0;
            if(l<x&&x<r){
                s=ps[x][l-1]+ps[x][n]-ps[x][r];
            }
            else{
                s=ps[x][r-1]-ps[x][l];
            }
            int z=s*(l+r);
            if(x<l)c[x][l]+=z;
            if(x<r)c[x][r]+=z;
        }
    }
    int mn=INF;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            mn=min(mn,cnt[i]+cnt[j]-c[i][j]);
        }
    }
    cout<<ans-mn<<endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    // cin>>t;
    while (t--) {
        solve();
    }
    return 0;
}

J. Determinant

竟然是随机一个不能整除的模数然后都对这个取模然后比较。

#include <bits/stdc++.h>
  
using namespace std;
  
typedef long long LL;
  
int MOD;
const int N = 110;
 
using ll = long long;
using u32 = uint32_t;
using u64 = uint64_t;
 
struct RandomGenerator {
    u64 state;
 
    RandomGenerator(u64 seed = chrono::steady_clock::now().time_since_epoch().count())
        : state(seed) {}
 
    u64 next_u64() {
        u64 z = (state += 0x9e3779b97f4a7c15ULL);
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
        z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
        return z ^ (z >> 31);
    }
 
    u32 next_u32() { return next_u64(); }
    ll next_i64() { return (ll)next_u64(); }
    int32_t next_i32() { return (int32_t)next_u32(); }
 
    static u64 power(u64 a, u64 b, u64 mod) {
        u64 res = 1;
        while (b) {
            if (b & 1) res = (__uint128_t)res * a % mod;
            a = (__uint128_t)a * a % mod;
            b >>= 1;
        }
        return res;
    }
 
    static bool is_prime(u64 n) {
        if (n < 2) return false;
        for (u64 p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
            if (n % p == 0) return n == p;
        }
        u64 d = n - 1, s = 0;
        while (!(d & 1)) d >>= 1, s++;
        for (u64 a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
            if (a % n == 0) continue;
            u64 x = power(a % n, d, n);
            if (x == 1 || x == n - 1) continue;
            bool ok = false;
            for (u64 r = 1; r < s; r++) {
                x = (__uint128_t)x * x % n;
                if (x == n - 1) {
                    ok = true;
                    break;
                }
            }
            if (!ok) return false;
        }
        return true;
    }
 
    int random_prime() {
        while (true) {
            int x = (next_i32() & ((1ULL << 30) - 1)) | (1ULL << 30) | 1;
            if (is_prime(x)) return x;
        }
    }
};
  
LL a[N][N];
 
LL power(LL n, LL p) {
    LL res = 1, base = n;
    while (p) {
        if (p & 1) res = res * base % MOD;
        base = base * base % MOD;
        p >>= 1;
    }
    return res;
}
  
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    RandomGenerator rnd;
    int T;
    cin >> T;
    while (T--) {
        int n;
        string s;
        cin >> n >> s;
        LL v = 0, t = 1;
        do {
            MOD = rnd.random_prime();
            for (char c : s) {
                v = (v * 10 + c - 48) % MOD;
            }
        } while (v == 0);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                cin >> a[i][j];
                a[i][j] = (a[i][j] + MOD) % MOD;
            }
        }
        for (int i = 1; i <= n; ++i) {
            if (!a[i][i]) {
                for (int j = i + 1; j <= n; ++j) {
                    if (a[j][i]) {
                        swap(a[i], a[j]);
                        t = t * power(MOD - 1, MOD - 2);
                        break;
                    }
                }
            }
            LL p = power(a[i][i], MOD - 2);
            t = t * a[i][i] % MOD;
            for (int j = i + 1; j <= n; ++j) {
                LL q = a[j][i] * p % MOD;
                for (int k = i; k <= n; ++k) {
                    a[j][k] = ((a[j][k] - q * a[i][k]) % MOD + MOD) % MOD;
                }
            }
        }
        cout << (t == v ? '+' : '-') << '\n';
    }
    return 0;
}

K. Search For Mafuyu

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;

    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i ++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }

    vector<int> dep(n + 1);

    auto dfs = [&](auto self, int u, int fa, int d) -> void {
        dep[u] = d;
        for (auto v : g[u]) if (v != u) {
            self(self, v, u, d + 1);
        }
    };
    dfs(dfs, 1, 0, 0);

    long double ans = 0;

    ll cur = 0;
    auto calc = [&](auto self, int u, int fa) -> void {
        sort(g[u].begin(), g[u].end(), [&](int x, int y){
            return dep[x] < dep[y];
        });
        ans += cur;
        for (int v : g[u]) if (v != fa) {
            cur ++;
            self(self, v, u);
            cur ++;
        }
    };
    calc(calc, 1, 0);
    // cout << ans << '\n';
    cout << fixed << setprecision(10);
    cout << ans / (n - 1) << '\n';
}

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

L. Strange Series

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#define int long long
#define vi vector<int>
using namespace std;
const int N = 5e5 + 5;
using ll = long long;
const int NTT_MOD = 998244353;
const int NTT_ROOT = 3;
int ntt_qpow(int a, int b) {
    int result = 1;
    while (b) {
        if (b & 1)
            result = 1LL * result * a % NTT_MOD;
        a = 1LL * a * a % NTT_MOD;
        b >>= 1;
    }
    return result;
}
void ntt(vector<int> &a, bool invert) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        while (j & bit) {
            j ^= bit;
            bit >>= 1;
        }
        j ^= bit;
        if (i < j)
            swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        int root = ntt_qpow(NTT_ROOT, (NTT_MOD - 1) / len);
        if (invert)
            root = ntt_qpow(root, NTT_MOD - 2);
        for (int i = 0; i < n; i += len) {
            int w = 1;
            for (int j = 0; j < len / 2; j++) {
                int x = a[i + j];
                int y = 1LL * a[i + j + len / 2] * w % NTT_MOD;
                a[i + j] = x + y;
                if (a[i + j] >= NTT_MOD)
                    a[i + j] -= NTT_MOD;
                a[i + j + len / 2] = x - y;
                if (a[i + j + len / 2] < 0) {
                    a[i + j + len / 2] += NTT_MOD;
                }
                w = 1LL * w * root % NTT_MOD;
            }
        }
    }
    if (invert) {
        int inv_n = ntt_qpow(n, NTT_MOD - 2);
        for (int &x : a) x = 1LL * x * inv_n % NTT_MOD;
    }
}
vector<int> ntt_mul(vector<int> a, vector<int> b) {
    if (a.empty() || b.empty())
        return {};
    int size = a.size() + b.size() - 1;
    int n = 1;
    while (n < size) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) {
        a[i] = 1LL * a[i] * b[i] % NTT_MOD;
    }
    ntt(a, true);
    a.resize(size);
    return a;
}
vector<int> poly_inv(vector<int> f, int n) {
    int f0 = (f[0] % NTT_MOD + NTT_MOD) % NTT_MOD;
    vector<int> g(1, ntt_qpow(f0, NTT_MOD - 2));
    for (int m = 1; m < n; m <<= 1) {
        int len = min(m << 1, n);
        vector<int> ff(len);
        for (int i = 0; i < len && i < (int)f.size(); i++) {
            ff[i] = f[i];
        }
        vector<int> t = ntt_mul(ff, g);
        t.resize(len);
        // t = 2 - f * g
        for (int &x : t) x = (NTT_MOD - x) % NTT_MOD;
        t[0] += 2;
        if (t[0] >= NTT_MOD)
            t[0] -= NTT_MOD;
        g = ntt_mul(g, t);
        g.resize(len);
    }
    g.resize(n);
    return g;
}
vector<int> poly_ln(vector<int> f, int n) {
    if (n == 1)
        return vector<int>(1);
    int lim = min(n, (int)f.size());
    vector<int> d(max(0ll, lim - 1));
    for (int i = 1; i < lim; i++) {
        d[i - 1] = 1LL * f[i] * i % NTT_MOD;
    }
    vector<int> g = ntt_mul(d, poly_inv(f, n));
    g.resize(n - 1);
    vector<int> iv(n + 1);
    iv[1] = 1;
    for (int i = 2; i <= n; i++) {
        iv[i] = 1LL * (NTT_MOD - NTT_MOD / i) * iv[NTT_MOD % i] % NTT_MOD;
    }
    vector<int> res(n);
    for (int i = 1; i < n; i++) {
        res[i] = 1LL * g[i - 1] * iv[i] % NTT_MOD;
    }
    return res;
}
vector<int> poly_exp(vector<int> f) {
    int n = f.size();
    vector<int> g(1, 1);
    for (int m = 1; m < n; m <<= 1) {
        int len = min(m << 1, n);
        vector<int> lng = poly_ln(g, len);
        vector<int> t(len);
        // t = 1 + f - ln(g)
        for (int i = 0; i < len; i++) {
            t[i] = f[i] - lng[i];
            if (t[i] < 0)
                t[i] += NTT_MOD;
        }
        t[0]++;
        if (t[0] >= NTT_MOD)
            t[0] -= NTT_MOD;
        g = ntt_mul(g, t);
        g.resize(len);
    }
    return g;
}
struct Comb {
    int n;
    int mod;
    vector<int> fac, invfac;

    Comb(int _n, int _mod) {
        n = _n;
        mod = _mod;
        fac.assign(n + 1, 1);
        invfac.assign(n + 1, 1);

        for (int i = 1; i <= n; i++) {
            fac[i] = fac[i - 1] * i % mod;
        }

        invfac[n] = qpow(fac[n], mod - 2);

        for (int i = n - 1; i >= 0; i--) {
            invfac[i] = invfac[i + 1] * (i + 1) % mod;
        }
    }

    int qpow(int a, int b) {
        int res = 1;
        while (b) {
            if (b & 1)
                res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
    int A(int n, int m) {
        if (m < 0 || m > n)
            return 0;
        return fac[n] * invfac[n - m] % mod;
    }
    int C(int n, int m) {
        if (m < 0 || m > n)
            return 0;
        return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
    }
};
Comb comb(N, NTT_MOD);

vi get(int n){
    vi e(n + 1);
    for (int i = 1; i <=n; i++) e[i] = comb.invfac[i];
    vi res=poly_exp(e);
    for(int i = 0; i <= n; i++) {
        res[i]*=comb.fac[i];
        res[i] %= NTT_MOD;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    vi f = get(1e5 + 1);


    
    int t;
    cin >> t;

    while (t --) {
        ll ans = 0;
        int n;
        cin >> n;
        for (int i = 0; i <= n; i ++) {
            ll x;
            cin >> x;
            ans += x * f[i];
            ans %= NTT_MOD;
        }
        cout << ans << '\n';
    }
}

其他没做的题

• Space Station
• Monitored Area
• Neural Network Counting
• Happy Alice
• Game Coin
• Permutation Pair
• Coloring Rectangles