A - World Cup

题意

给你一个数$x$，询问下一个$ \mod 4 \equiv 2$的数是多少

题解

直接模拟即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    cin >> n;
    while (n % 4 != 2) ++ n;
    cout << n << '\n';
    return 0;
}

B - Triangle (Easier)

题意

给你一张$n$个点，$m$条边的无向图，询问形如$a < b < c$且$a,b,c$之间都有连边的$(a,b,c)$三元组个数

题解

注意到$n \leq 100$，直接暴力枚举即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    vector< vector< int > > d(105, vector< int > (105));
    while (m -- ) {
        int u, v;
        cin >> u >> v;
        d[u][v] = d[v][u] = true;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++ i) {
        for (int j = i + 1; j <= n; ++ j) {
            for (int k = j + 1; k <= n; ++ k) {
                if (d[i][j] && d[j][k] && d[i][k]) {
                    ++ ans;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

C - Min Max Pair

题意

一个长度为$n$的序列，且$1 \leq a_i \leq n(1 \leq i \leq n)$

求出满足$i < j$且$\min (a_i,a_j)=i, \max (a_i,a_j)=j$的二元组$(i,j)$个数

题解

我们对每一个$a_i$进行枚举

  • 首先分析$a_i=i$的情况

    答案即为$a_j=j(i+1 \leq j \leq n)$的个数

  • 再来分析$a_i \neq i$的情况

    答案即为$a_i=j$且$a_j=i$的个数

最后将答案加起来即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    cin >> n;
    vector< int > a(n), cnt(n), suf(n);
    for (int i = 0; i < n; ++ i) {
        cin >> a[i];
        -- a[i];
        ++ cnt[a[i]];
    }
    LL ans1 = 0, ans2 = 0;
    suf[n - 1] = a[n - 1] == n - 1;
    for (int i = n - 2; i >= 0; -- i) {
        suf[i] = suf[i + 1] + (a[i] == i);
    }
    for (int i = 0; i <= n - 1; ++ i) {
        if (a[i] == i && i + 1 <= n - 1) {
            ans1 += suf[i + 1];
        }
        if (a[i] != i) {
            ans2 += a[a[i]] == i;
        }
    }
    cout << ans1 + ans2 / 2 << '\n';
    return 0;
}

D - I Hate Non-integer Number

题意

给你一个长度为$n$的序列，你可以在其中选任意正整数个数，求选出的数的平均数为偶数的个数

题解

这题一眼$dp$，但是奈何我脑子笨一直没调对，好在最后半小时调出来了，太菜了555

我们定义$ans_i$为选$i$个数，其平均数为偶数的个数

我们定义$dp[t][i][j][k]$代表选$t$个数的方案中前$i$个数选$j$个数，它们的和$\mod t \equiv k$的方案数

注意到$ans_i,ans_j(i \neq j)$之间没有任何关联，所以$dp$数组的第一维可以优化掉

状态转移方程也是十分显然

$dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][(k-a[i])\mod t+t)\mod t]$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;

LL dp[102][102][102];
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    cin >> n;
    vector< int > a(n + 1);
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
    }
    LL ans = 0;
    for (int p = 1; p <= n; ++ p) {
        memset(dp, 0, sizeof dp);
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; ++ i) {
            dp[i][0][0] = 1;
            for (int j = 1; j <= i; ++ j) {
                for (int k = 0; k < p; ++ k) {
                    int kk = ((k - a[i]) % p + p) % p;
                    dp[i][j][k] += dp[i - 1][j - 1][kk];
                    dp[i][j][k] %= MOD;
                    dp[i][j][k] += dp[i - 1][j][k];
                    dp[i][j][k] %= MOD;
                }
            }
        }
        ans = (ans + dp[n][p][0]) % MOD;
    }
    cout << ans << '\n';
    return 0;
}

E - Red and Blue Graph

题意

给你$n$个点，$m$条边的无向图，并且你可以将其中的$k$个点标记为红色，其余的标记为蓝色，求两端为不同颜色的边的个数为偶数的方案数

题解

这题真是你敢猜，就能对

首先我们注意到答案跟节点的编号没有关系，我们从节点的度数出发，当相邻的节点涂同一个颜色时，它对答案的奇偶性不会发生影响，度数为偶数的节点涂成红色会产生偶数条边，度数为基数的节点涂成红色会产生奇数条边。这个结论可以画几个图验证一下，所以现在的问题是保证选择的节点中，度数为奇数的点的个数为偶数，度数为偶数的点随意，原问题转化为排列组合问题。

$ans = \sum \binom {x}{cnt_1} \times \binom{k-x}{cnt_0}$ 其中$x % \equiv 0$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;

constexpr int P = 998244353;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(i64 x) : x(norm(x % P)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};
int n, m, k;
int deg[N];
Z inv[N], fac[N], finv[N];
void Pre_Work() {
    fac[0] = fac[1] = 1;
    inv[1] = 1;
    finv[0] = finv[1] = 1;
    for(int i = 2; i < N; ++ i) {
        fac[i] = fac[i - 1] * i;
        inv[i] = MOD - MOD / i * inv[MOD % i];
        finv[i] = finv[i - 1] * inv[i];
    }
}
Z C(int x, int y) {
    if (x < y) return 0;
    return fac[x] * finv[x - y] * finv[y];
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    Pre_Work();
    cin >> n >> m >> k;
    for (int i = 1; i <= m; ++ i) {
        int u, v;
        cin >> u >> v;
        ++ deg[v];
        ++ deg[u];
    }
    vector< int > cnt(2);
    for (int i = 1; i <= n; ++ i) {
        ++ cnt[deg[i] & 1];
    }
    Z ans = 0;
    if (k & 1) {
        for (int i = 1; i <= k; i += 2) {
            ans += C(cnt[0], i) * C(cnt[1], k - i);
        }
    } else {
        for (int i = 0; i <= k; i += 2) {
            ans += C(cnt[0], i) * C(cnt[1], k - i);
        }
    }
    cout << ans << '\n';
    return 0;
}

后面几题再补。。。