2025年2月竞赛好题精选

本文精选了2025年2月的四道高质量竞赛题目，涉及UOJ、LOJ、AtCoder等平台的经典题目。

一、UOJ Round 29 B - 数字生命

这道题目首先考虑差分操作。差分后若为正数，则视为起点；若为负数，则视为终点。随后问题转化为对每一对起点和终点进行配对，并插入若干区间覆盖。

我们采用集合幂级数的思想。设 $F_{i,j}$ 表示从第 $i$ 个起点到第 $j$ 个终点的可行集合，赋予随机权值，乘法定义为子集卷积。答案集合为：

$$\sum_{p} \prod_{i} F_{i,p_i}$$

和积式不易直接计算。注意到乘以额外因子不会影响结果，因此可以转化为计算行列式：

$$\sum_{p} \mathrm{sgn}(p) \prod_{i} F_{i,p_i}$$

子集卷积计算较为困难，可改为或卷积。若集合中元素进行或运算，则 $\sum \mathrm{len}$ 会减小，进行判断即可。

具体实现时，使用FWT计算每个集合幂级数的点值，然后计算行列式，最后通过IFWT得到答案。时间复杂度为 $O(2^m m^3)$。

参考实现（C++）

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

const int MAXN = 100005;
const int MAXM = 17;
const int MOD = 998244353;

inline int addMod(int x, int y) { 
    int res = x + y;
    if (res >= MOD) res -= MOD;
    return res;
}

inline void addAssign(int &x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}

inline int subMod(int x, int y) { 
    if (x < y) return x - y + MOD;
    return x - y;
}

inline void subAssign(int &x, int y) {
    x -= y;
    if (x < 0) x += MOD;
}

inline int mulMod(long long x, long long y) { 
    return (int)((x * y) % MOD);
}

inline void mulAssign(int &x, int y) {
    x = (int)((1LL * x * y) % MOD);
}

int powerMod(int x, int y) {
    int result = 1;
    while (y) {
        if (y & 1) mulAssign(result, x);
        mulAssign(x, x);
        y >>= 1;
    }
    return result;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int mainCount, targetM;
int diffArr[MAXN], startPos[MAXN], endPos[MAXN];
int elementSum[1 << MAXM];
int fwtData[1 << MAXM][MAXM][MAXM];
int detValue[1 << MAXM];

void combineMatrix(int dest[MAXM][MAXM], int src[MAXM][MAXM]) {
    for (int i = 0; i < mainCount; ++i)
        for (int j = 0; j < mainCount; ++j)
            addAssign(dest[i][j], src[i][j]);
}

void fwtOr(int limit) {
    for (int step = 1; step < limit; step <<= 1) {
        for (int base = 0; base < limit; base += (step << 1)) {
            for (int k = 0; k < step; ++k) {
                combineMatrix(fwtData[base + k + step], fwtData[base + k]);
            }
        }
    }
}

void ifwtOr(int limit) {
    for (int step = 1; step < limit; step <<= 1) {
        for (int base = 0; base < limit; base += (step << 1)) {
            for (int k = 0; k < step; ++k) {
                subAssign(detValue[base + k + step], detValue[base + k]);
            }
        }
    }
}

int calculateDet(int matrix[MAXM][MAXM], int n) {
    int result = 1;
    int weight = 1;
    
    for (int i = 0; i < n; ++i) {
        if (!matrix[i][i]) {
            for (int row = i + 1; row < n; ++row) {
                if (matrix[row][i]) {
                    swap(matrix[i], matrix[row]);
                    result = subMod(0, result);
                    break;
                }
            }
        }
        if (!matrix[i][i]) return 0;
        
        mulAssign(result, matrix[i][i]);
        
        for (int row = i + 1; row < n; ++row) {
            mulAssign(weight, matrix[i][i]);
            int factor = matrix[row][i];
            for (int col = i; col < n; ++col) {
                matrix[row][col] = subMod(
                    mulMod(matrix[i][i], matrix[row][col]),
                    mulMod(matrix[i][col], factor)
                );
            }
        }
    }
    
    return mulMod(result, powerMod(weight, MOD - 2));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int totalN;
    cin >> totalN >> targetM;
    
    for (int i = 1; i <= totalN; ++i) cin >> diffArr[i];
    
    int totalSum = 0;
    for (int i = 1; i <= totalN; ++i) totalSum += diffArr[i];
    
    for (int i = totalN + 1; i >= 1; --i) diffArr[i] -= diffArr[i - 1];
    
    mainCount = 0;
    for (int i = 1; i <= totalN + 1; ++i) {
        while (diffArr[i] > 0) {
            diffArr[i]--;
            startPos[mainCount++] = i;
        }
    }
    
    mainCount = 0;
    for (int i = 1; i <= totalN + 1; ++i) {
        while (diffArr[i] < 0) {
            diffArr[i]++;
            endPos[mainCount++] = i;
        }
    }
    
    if (mainCount > targetM) {
        for (int i = 0; i < (1 << targetM); ++i) cout << 0;
        cout << "\n";
        return 0;
    }
    
    vector<int> coeff(targetM);
    for (int i = 0; i < targetM; ++i) cin >> coeff[i];
    
    for (int mask = 0; mask < (1 << targetM); ++mask) {
        elementSum[mask] = 0;
        for (int i = 0; i < targetM; ++i) {
            if (mask & (1 << i)) elementSum[mask] += coeff[i];
        }
        for (int i = 0; i < mainCount; ++i) {
            for (int j = 0; j < mainCount; ++j) {
                if (endPos[j] - startPos[i] == elementSum[mask]) {
                    fwtData[mask][i][j] = rng() % MOD;
                }
            }
        }
    }
    
    fwtOr(1 << targetM);
    
    for (int mask = 0; mask < (1 << targetM); ++mask) {
        detValue[mask] = calculateDet(fwtData[mask], mainCount);
    }
    
    ifwtOr(1 << targetM);
    
    for (int mask = 0; mask < (1 << targetM); ++mask) {
        cout << (totalSum == elementSum[mask] && detValue[mask]);
    }
    cout << "\n";
    
    return 0;
}

二、P10063 [SNOI2024] 平方数

本题值域非常大，无法直接分解质因数。我们考虑在模随机大质数下进行判断。

在模一个大质数 $P$ 时，约有一半的数是二次剩余，可视为 $\frac{1}{2}$ 的概率。因此随机选取 $T=40$ 个大质数进行判断，错误概率仅为 $\frac{1}{2^{40}}$，可忽略不计。

判断二次剩余的方法是计算 $a^{\frac{P+1}{2}} \bmod P$，结果为 $1$ 或 $-1$。对于每个 $a_i$ 单独计算其在各模数下的值，区间内若有偶数个 $-1$，则该区间合法。可以用哈希表快速统计合法区间数量。

时间复杂度为 $O(T \cdot n \log n)$。

参考实现（C++）

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

using int64 = long long;
using i128 = __int128_t;

const int MAXN = 300005;
const int CHECK_TIMES = 40;
const int OUTPUT_LIMIT = 100000;

int elementCount;
i128 original[MAXN];
int64 prefixProd[CHECK_TIMES];
int64 legendreSymbol[MAXN];
int uniqArr[MAXN], uniqSize;
vector<int> bucket[MAXN];

int64 basePrimes[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
int64 randomPrimes[CHECK_TIMES];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int64 generateRandom() {
    return (int64)(rng() >> 3) * rng() + rng();
}

int64 multiplyMod(int64 a, int64 b, int64 mod) {
    __int128_t res = (__int128_t)a * b;
    res %= mod;
    return (int64)res;
}

int64 powerMod(int64 base, int64 exp, int64 mod) {
    int64 result = 1;
    while (exp) {
        if (exp & 1) result = multiplyMod(result, base, mod);
        base = multiplyMod(base, base, mod);
        exp >>= 1;
    }
    return result;
}

bool millerRabin(int64 n, int64 a) {
    if (n < 2) return false;
    if (n % a == 0) return n == a;
    
    int64 d = n - 1;
    int r = 0;
    while ((d & 1) == 0) {
        d >>= 1;
        ++r;
    }
    
    int64 x = powerMod(a, d, n);
    if (x == 1 || x == n - 1) return true;
    
    for (int i = 0; i < r - 1; ++i) {
        x = multiplyMod(x, x, n);
        if (x == n - 1) return true;
    }
    return false;
}

bool isPrime(int64 n) {
    if (n < 2) return false;
    for (int64 p : basePrimes) {
        if (n == p) return true;
        if (n % p == 0) return false;
    }
    for (int i = 0; i < 7; ++i) {
        if (!millerRabin(n, basePrimes[i])) return false;
    }
    return true;
}

i128 readInteger() {
    i128 result = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        result = result * 10 + (c - '0');
        c = getchar();
    }
    return result;
}

void initializePrimes() {
    for (int i = 0; i < CHECK_TIMES; ++i) {
        int64 x = generateRandom();
        while (!isPrime(x)) x = generateRandom();
        randomPrimes[i] = x;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    elementCount = readInteger();
    for (int i = 1; i <= elementCount; ++i) original[i] = readInteger();
    
    initializePrimes();
    
    for (int i = 0; i < CHECK_TIMES; ++i) prefixProd[i] = 1;
    
    for (int i = elementCount; i >= 1; --i) {
        for (int j = 0; j < CHECK_TIMES; ++j) {
            prefixProd[j] = multiplyMod(prefixProd[j], original[i] % randomPrimes[j], randomPrimes[j]);
            int64 val = powerMod(prefixProd[j] % randomPrimes[j], (randomPrimes[j] - 1) >> 1, randomPrimes[j]);
            if (val != 1) legendreSymbol[i] |= (1LL << j);
        }
    }
    
    for (int i = 1; i <= elementCount + 1; ++i) uniqArr[++uniqSize] = legendreSymbol[i];
    sort(uniqArr + 1, uniqArr + uniqSize + 1);
    uniqSize = unique(uniqArr + 1, uniqArr + uniqSize + 1) - uniqArr - 1;
    
    for (int i = 1; i <= elementCount + 1; ++i) {
        legendreSymbol[i] = lower_bound(uniqArr + 1, uniqArr + uniqSize + 1, legendreSymbol[i]) - uniqArr;
    }
    
    int64 answer = 0;
    vector<pair<int, int>> resultIntervals;
    
    for (int i = elementCount + 1; i >= 1; --i) {
        answer += bucket[legendreSymbol[i]].size();
        bucket[legendreSymbol[i]].push_back(i);
    }
    
    for (int i = 1; i <= elementCount; ++i) {
        reverse(bucket[i].begin(), bucket[i].end());
    }
    
    for (int i = 1; i <= elementCount; ++i) {
        for (int r : bucket[legendreSymbol[i]]) {
            if (r > i) {
                resultIntervals.push_back({i, r - 1});
                if ((int)resultIntervals.size() == OUTPUT_LIMIT) break;
            }
        }
        if ((int)resultIntervals.size() == OUTPUT_LIMIT) break;
    }
    
    cout << answer << "\n";
    for (auto &pr : resultIntervals) {
        cout << pr.first << " " << pr.second << "\n";
    }
    
    return 0;
}

三、AGC070C - No Streak

本题要求Alice的胜利次数始终大于Bob。对于不能连胜的限制，相当于对折线形态有约束，采用反射容斥方法处理。

定义 $F(A,B,E)$ 为Alice胜 $A$ 局、Bob胜 $B$ 局、平局 $E$ 局，且没有连胜情况的方案数，可在 $O(n)$ 时间内求得。

接下来考虑对直线 $y = x + 1$ 的情况进行分类讨论：

情况一：到达 $y = x + 1$ 后立即右转。这种情况翻转后仍会有连胜，需要插入一个向上步骤，方案为 $F(A+1, B-1, E)$。

情况二：到达 $y = x + 1$ 后停歇（平局）。考虑插入一个停歇步骤，方案为 $F(A+1, B-1, E-1)$。但去掉停歇后翻转可能仍有连胜，需再插入一个向上步骤，为 $F(A+1, B-1, E-1)$。

综上，最终答案为：

$$F(A,B,E) - F(A,B-1,E) - F(A+1,B-1,E) - F(A,B-1,E-1)$$

时间复杂度为 $O(n)$。

参考实现（C++）

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

const int MAXN = 30000005;
const int MOD = 1000000007;

inline int addMod(int x, int y) {
    int res = x + y;
    if (res >= MOD) res -= MOD;
    return res;
}

inline void addAssign(int &x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}

inline int subMod(int x, int y) {
    if (x < y) return x - y + MOD;
    return x - y;
}

inline void subAssign(int &x, int y) {
    x -= y;
    if (x < 0) x += MOD;
}

inline int mulMod(long long x, long long y) {
    return (int)((x * y) % MOD);
}

inline void mulAssign(int &x, int y) {
    x = (int)((1LL * x * y) % MOD);
}

int mulMultiple(initializer_list<int> values) {
    int result = 1;
    for (int v : values) mulAssign(result, v);
    return result;
}

int powerMod(int x, int y) {
    int result = 1;
    while (y) {
        if (y & 1) mulAssign(result, x);
        mulAssign(x, x);
        y >>= 1;
    }
    return result;
}

int totalN, aliceWins, bobWins, draws;
int factorial[MAXN], invFactorial[MAXN];

void precompute(int n) {
    factorial[0] = 1;
    for (int i = 1; i <= n; ++i) factorial[i] = mulMod(factorial[i - 1], i);
    invFactorial[n] = powerMod(factorial[n], MOD - 2);
    for (int i = n; i >= 1; --i) invFactorial[i - 1] = mulMod(invFactorial[i], i);
}

int combination(int n, int k) {
    if (n < k || k < 0) return 0;
    return mulMultiple({factorial[n], invFactorial[k], invFactorial[n - k]});
}

int calculateF(int A, int B, int E) {
    if (B == 0) return combination(E + 1, A);
    
    int result = 0;
    for (int i = 1; i <= B; ++i) {
        addAssign(result, mulMultiple({
            combination(B - 1, i - 1),
            combination(A - 1, i - 2),
            combination(E + i * 2 - 1, A + B)
        }));
        addAssign(result, mulMultiple({
            2,
            combination(B - 1, i - 1),
            combination(A - 1, i - 1),
            combination(E + i * 2, A + B)
        }));
        addAssign(result, mulMultiple({
            combination(B - 1, i - 1),
            combination(A - 1, i),
            combination(E + i * 2 + 1, A + B)
        }));
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> totalN >> aliceWins >> bobWins;
    draws = totalN - aliceWins - bobWins;
    
    precompute(MAXN - 1);
    
    int answer = calculateF(aliceWins, bobWins, draws);
    subAssign(answer, calculateF(aliceWins, bobWins - 1, draws));
    subAssign(answer, calculateF(aliceWins + 1, bobWins - 1, draws - 1));
    subAssign(answer, calculateF(aliceWins, bobWins - 1, draws - 1));
    
    cout << answer << "\n";
    return 0;
}

四、AGC070B - Odd Namori

本题图论限制和权值较为特殊，需要使用容斥方法处理。

设 $F(G,S)$ 为图 $G$ 中点集 $S$ 的诱导子图。若该诱导子图由若干环构成，其中偶环有 $c$ 个，则权值为 $(-1)^c$。求 $\sum_{S} F(G,S)$。

若图 $G$ 包含偶环，其权值经容斥后为 $0$；否则权值为 $2^c$，其中 $c$ 为奇环数。

接下来枚举 $S$，计算所有 $\sum_{G} F(G,S)$。不在 $S$ 中的点可直接计算方案数。

对于 $S$ 内部，考虑若无限制，可交换两点出边进行容斥，方案数为 $[|S|=1]$。考虑有限制情况，继续容斥去除不合法情况。

由于 $S$ 的诱导子图需变为若干环，不能存在两点指向同一点，只剩下链状结构。若有多条链，可继续容斥掉。

有贡献的情况必为单链，且乘上后续容斥系数后贡献均为 $1$，直接枚举链的长度即可。

时间复杂度为 $O(n)$。

参考实现（C++）

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

const int MAXN = 100005;
const int MOD = 998244353;

inline int addMod(int x, int y) {
    int res = x + y;
    if (res >= MOD) res -= MOD;
    return res;
}

inline void addAssign(int &x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}

inline int mulMod(long long x, long long y) {
    return (int)((x * y) % MOD);
}

inline void mulAssign(int &x, int y) {
    x = (int)((1LL * x * y) % MOD);
}

int powerMod(int x, int y) {
    int result = 1;
    while (y) {
        if (y & 1) mulAssign(result, x);
        mulAssign(x, x);
        y >>= 1;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int vertexCount;
    cin >> vertexCount;
    
    vector<int> parent(vertexCount + 1);
    for (int i = 2; i <= vertexCount; ++i) cin >> parent[i];
    
    vector<int> depth(vertexCount + 1);
    depth[1] = 1;
    for (int i = 2; i <= vertexCount; ++i) depth[i] = depth[parent[i]] + 1;
    
    int result = mulMod(vertexCount, powerMod(vertexCount - 1, vertexCount - 1));
    
    for (int i = 1; i <= vertexCount; ++i) {
        addAssign(result, powerMod(vertexCount - 1, vertexCount - depth[i]));
    }
    
    vector<int> suffix(vertexCount + 2, 0);
    for (int i = 2; i <= vertexCount; ++i) suffix[depth[i] - 1]++;
    
    for (int i = vertexCount; i >= 1; --i) suffix[i] += suffix[i + 1];
    
    for (int i = 1; i <= vertexCount - 1; ++i) {
        addAssign(result, mulMod(mulMod(vertexCount, suffix[i]), powerMod(vertexCount - 1, vertexCount - i - 1)));
    }
    
    cout << result << "\n";
    return 0;
}

总结

以上四道题目分别涉及集合幂级数、概率与数论、反射容斥以及图论容斥等高级算法技巧，是非常值得深入研究的竞赛好题。