NOTE
比赛链接：Atcoder Beginner Contest 458

A - Chompers#

关键词：签到

Code#

1
// Problem: AT ABC458 A
2
// Contest: AtCoder - AtCoder Beginner Contest 458
3
// URL: https://atcoder.jp/contests/abc458/tasks/abc458_a
4
// Time: 2026-05-16 20:00:05
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    string s;
29
    int n;
30

31
    cin >> s >> n;
32

33
    for (int i = n; i < s.size() - n; i++)
34
        cout << s[i];
35
}
36

37
int main()
38
{
39
    fastio();
40

41
    int T = 1;
42
    // cin >> T;
43

44
    while (T--)
45
        solve();
46

47
    return 0;
48
}

B - Count Adjacent Cells#

关键词：分类讨论

思路#

考虑讨论三种情况。当 $n$ 和 $m$ 都为 $1$ 时，答案是 $0$ ，当二者中有一个为 $1$ 时，边界是单联通的，其余所有元素都是双联通。对于剩下的情况，四个角落是双联通，四条外侧边的中间部分是三联通，内部都是四联通。

Code#

1
// Problem: AT ABC458 B
2
// Contest: AtCoder - AtCoder Beginner Contest 458
3
// URL: https://atcoder.jp/contests/abc458/tasks/abc458_b
4
// Time: 2026-05-16 20:00:06
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
int n, m;
27

28
bool check(int x, int y)
29
{
30
    if (x == 1 && y == 1)
31
        return true;
32
    if (x == 1 && y == m)
33
        return true;
34
    if (x == n && y == 1)
35
        return true;
36
    if (x == n && y == m)
37
        return true;
38

39
    return false;
40
}
41

42
void solve()
43
{
44
    cin >> n >> m;
45

46
    if (n == 1 && m == 1)
47
    {
48
        cout << 0 << endl;
49
        return;
50
    }
51

52
    for (int i = 1; i <= n; i++)
53
    {
54
        for (int j = 1; j <= m; j++)
55
        {
56
            if (n == 1 || m == 1)
57
            {
58
                if (check(i, j))
59
                    cout << 1 << " ";
60
                else
61
                    cout << 2 << " ";
62
                continue;
63
            }
64

65
            if (check(i, j))
66
            {
67
                cout << 2 << " ";
68
                continue;
69
            }
70
            if (i == 1 || i == n || j == m || j == 1)
71
            {
72
                cout << 3 << " ";
73
                continue;
74
            }
75
            cout << 4 << " ";
76
        }
77
        cout << endl;
78
    }
79
}
80

81
int main()
82
{
83
    fastio();
84

85
    int T = 1;
86
    // cin >> T;
87

88
    while (T--)
89
        solve();
90

91
    return 0;
92
}

C - C Stands for Center#

关键词：推公式

思路#

对于每个 $C$ ，由于要求子区间长度为奇数，所以我们考虑以 $C$ 为中心向两侧扩展。容易知道，扩展的最远长度取决于它两侧元素数量的最小值，即 min(i, n - 1 - i)（下标从 $0$ 开始）。

注意还要加 $1$ ，也就是不往外扩展的情况。此时子数组为 $C$ 。

Code#

1
// Problem: AT ABC458 C
2
// Contest: AtCoder - AtCoder Beginner Contest 458
3
// URL: https://atcoder.jp/contests/abc458/tasks/abc458_c
4
// Time: 2026-05-16 20:00:07
5

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

9
// clang-format off
10
#define endl '\n'
11
#define all(x) (x).begin(), (x).end()
12
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
13
// clang-format on
14

15
using ll = long long;
16
using ull = unsigned long long;
17
using pii = pair<int, int>;
18
using pdd = pair<double, double>;
19
using pll = pair<long long, long long>;
20
using i128 = __int128;
21

22
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
23
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
24
const int inf = 0x3f3f3f3f;
25
const int N = 0;
26

27
void solve()
28
{
29
    string s;
30
    cin >> s;
31

32
    ll n = s.size();
33
    vector<ll> pos;
34

35
    ll res = 0;
36
    for (ll i = 0; i < s.size(); i++)
37
    {
38
        if (s[i] == 'C')
39
        {
40
            ll tmp = min(i, n - 1 - i);
41
            res += tmp + 1;
42
        }
43
    }
44

45
    cout << res << endl;
46
}
47

48
int main()
49
{
50
    fastio();
51

52
    int T = 1;
53
    // cin >> T;
54

55
    while (T--)
56
        solve();
57

58
    return 0;
59
}

D - Chalkboard Median#

关键词：STL

思路#

一开始交了一发 $TLE$ ，考虑的是把所有数加入进一个 Multiset 里，并每次计算出中间位置的迭代器，但迭代器移动函数 advance() 和 distance() 函数都是 $O(n)$ 的，会超时。

我们考虑优化策略。注意到每次增加两个数，我们可以通过检验两个数和现有中间的数的大小关系。

假如现在集合里只有一个元素 $x$ ，如果新加入两个比 $x$ 小的数，显然迭代器应该往左移动一个位置。同理，如果新加入两个比 $x$ 大（或者等于 $x$ ）的数，迭代器应该往右移动一个位置。如果一大一小，迭代器保持不动即可。

NOTE
在 C++ 的 std::multiset 中，如果插入一个和已有元素相等的数，默认会把它插入到相同元素的最右侧。
也就是说，如果 p == *it，它会被放到 it 的右边，不会影响 it 左侧的计数。

Code#

1
// Problem: AT ABC458 D
2
// Contest: AtCoder - AtCoder Beginner Contest 458
3
// URL: https://atcoder.jp/contests/abc458/tasks/abc458_d
4
// Time: 2026-05-16 20:00:08
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int x, q;
29
    cin >> x >> q;
30

31
    multiset<int> s;
32
    s.insert(x);
33

34
    auto it = s.begin();
35

36
    while (q--)
37
    {
38
        int p, y;
39
        cin >> p >> y;
40

41
        s.insert(p);
42
        s.insert(y);
43

44
        int cnt = 0;
45
        if (p < *it)
46
            cnt++;
47
        if (y < *it)
48
            cnt++;
49

50
        if (cnt == 2)
51
            --it;
52
        else if (cnt == 0)
53
            ++it;
54

55
        cout << *it << endl;
56
    }
57
}
58

59
int main()
60
{
61
    fastio();
62

63
    int T = 1;
64
    // cin >> T;
65

66
    while (T--)
67
        solve();
68

69
    return 0;
70
}

E - Count 123#

关键词：组合数学

思路#

注意到 $2$ 是万能数字，我们考虑先排出一个只有 $1$ 和 $3$ 的序列，在这个序列中 $1$ 和 $3$ 允许相邻，但每一次相邻都必须在中间放入至少一个 $2$ 。

假设我们排出的 1、3 序列中，恰好有 $c$ 个交界处（比如 1 1 3 1 中，1到3有 1 个，3到1有 1 个，共 2 个交界）。为了修复这 $c$ 个非法交界，我们必须强制消耗 $c$ 个 2垫在中间。原本有 $X_2$ 个 2，强制消耗了 $c$ 个，还剩 $(X_2 - c)$ 个 2。

现在 1 和 3 的总数是 $(X_1 + X_3)$ 个，它们之间以及最左最右，一共提供了 $(X_1 + X_3 + 1)$ 个空位。

把剩下的 $(X_2 - c)$ 个相同的 2，放入这 $(X_1 + X_3 + 1)$ 个允许为空的槽位里，方案数为：

$\binom{(X_2 - c) + (X_1 + X_3 + 1) - 1}{(X_1 + X_3 + 1) - 1} = \binom{X_1 + X_2 + X_3 - c}{X_1 + X_3}$

下面我们考虑如何计算交界的数量。也就是有多少种排法，能让 1 和 3 产生恰好 $c$ 个交界？

我们设 $k$ 为一个基础块数，分奇偶讨论：

当 $c = 2k - 1$ （奇数个交界）：

序列一定是 1...3 或 3...1 这样交替。这意味着 1 有 $k$ 个段，3 也有 $k$ 个段。

将 $X_1$ 分成 $k$ 段方案数是 $\binom{X_1-1}{k-1}$ ，将 $X_3$ 分成 $k$ 段是 $\binom{X_3-1}{k-1}$ 。

两种开头方式，总排法为：

$2 \times \binom{X_1 - 1}{k - 1} \times \binom{X_3 - 1}{k - 1}$
当 $c = 2k$ （偶数个交界）：

序列一定是 1...1 或 3...3 这样交替。
- 如果是 1...1：1 有 $k+1$ 个段，3 有 $k$ 个段。排法为 $\binom{X_1-1}{k} \times \binom{X_3-1}{k-1}$ 。
- 如果是 3...3：1 有 $k$ 个段，3 有 $k+1$ 个段。排法为 $\binom{X_1-1}{k-1} \times \binom{X_3-1}{k}$ 。
  
  总排法就是这两者相加。

我们只需要枚举 $k$ ，算出对应的 $c$ ，把排法数 $\times$ 剩下的随便放 2 的方案数累加起来即可。

Code#

1
// Problem: AT ABC458 E
2
// Contest: AtCoder - AtCoder Beginner Contest 458
3
// URL: https://atcoder.jp/contests/abc458/tasks/abc458_e
4
// Time: 2026-05-16 20:00:09
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 3e6 + 5;
25

26
using u32 = uint32_t;
27
using u64 = uint64_t;
28

29
template<class T>
30
constexpr T power(T a, u64 b, T res = 1)
31
{
32
    for (; b != 0; b /= 2, a *= a)
33
    {
34
        if (b & 1)
35
            res *= a;
36
    }
37
    return res;
38
}
39

40
template<class U, U P>
41
struct ModIntBase
42
{
43
public:
44
    U x;
45
    constexpr ModIntBase() : x(0)
46
    {
47
    }
48

49
    constexpr ModIntBase(long long x_)
50
    {
51
        long long v = x_ % (long long) P;
52
        if (v < 0)
53
            v += (long long) P;
54
        x = (U) v;
55
    }
56

57
    constexpr static U mod()
58
    {
59
        return P;
60
    }
61
    constexpr U val() const
62
    {
63
        return x;
64
    }
65

66
    constexpr ModIntBase operator-() const
67
    {
68
        return ModIntBase(x == 0 ? 0 : P - x);
69
    }
70

71
    constexpr ModIntBase inv() const
72
    {
73
        return power(*this, P - 2);
74
    }
75

76
    constexpr ModIntBase &operator*=(const ModIntBase &rhs) &
77
    {
78
        x = (u64) x * rhs.x % P;
79
        return *this;
80
    }
81
    constexpr ModIntBase &operator+=(const ModIntBase &rhs) &
82
    {
83
        x += rhs.x;
84
        if (x >= P)
85
            x -= P;
86
        return *this;
87
    }
88
    constexpr ModIntBase &operator-=(const ModIntBase &rhs) &
89
    {
90
        if (x < rhs.x)
91
            x += P;
92
        x -= rhs.x;
93
        return *this;
94
    }
95
    constexpr ModIntBase &operator/=(const ModIntBase &rhs) &
96
    {
97
        return *this *= rhs.inv();
98
    }
99

100
    constexpr ModIntBase &operator++() &
101
    {
102
        x++;
103
        if (x == P)
104
            x = 0;
105
        return *this;
106
    }
107
    constexpr ModIntBase &operator--() &
108
    {
109
        if (x == 0)
110
            x = P;
111
        x--;
112
        return *this;
113
    }
114

115
    constexpr ModIntBase operator++(int)
116
    {
117
        ModIntBase res = *this;
118
        ++(*this);
119
        return res;
120
    }
121
    constexpr ModIntBase operator--(int)
122
    {
123
        ModIntBase res = *this;
124
        --(*this);
125
        return res;
126
    }
127

128
    friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs)
129
    {
130
        return lhs *= rhs;
131
    }
132
    friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs)
133
    {
134
        return lhs += rhs;
135
    }
136
    friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs)
137
    {
138
        return lhs -= rhs;
139
    }
140
    friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs)
141
    {
142
        return lhs /= rhs;
143
    }
144

145
    friend istream &operator>>(istream &is, ModIntBase &a)
146
    {
147
        long long v;
148
        is >> v;
149
        a = ModIntBase(v);
150
        return is;
151
    }
152
    friend ostream &operator<<(ostream &os, const ModIntBase &a)
153
    {
154
        return os << a.val();
155
    }
156
    friend bool operator==(const ModIntBase &lhs, const ModIntBase &rhs)
157
    {
158
        return lhs.val() == rhs.val();
159
    }
160

161
    friend bool operator!=(const ModIntBase &lhs, const ModIntBase &rhs)
162
    {
163
        return lhs.val() != rhs.val();
164
    }
165
};
166

167
constexpr u32 MOD = 998244353;
168
using Z = ModIntBase<u32, MOD>;
169

170
struct Comb
171
{
172
    int n;
173
    vector<Z> _fac;
174
    vector<Z> _invfac;
175
    vector<Z> _inv;
176

177
    Comb() : n(1), _fac(2), _invfac(2), _inv(2)
178
    {
179
        _fac[0] = _fac[1] = 1;
180
        _invfac[0] = _invfac[1] = 1;
181
        _inv[1] = 1;
182
    }
183

184
    Comb(int n) : Comb()
185
    {
186
        init(n);
187
    }
188

189
    void init(int m)
190
    {
191
        if (m <= n)
192
            return;
193

194
        int old = n;
195

196
        _fac.resize(m + 1);
197
        _invfac.resize(m + 1);
198
        _inv.resize(m + 1);
199

200
        for (int i = old + 1; i <= m; i++)
201
        {
202
            _fac[i] = _fac[i - 1] * i;
203
        }
204

205
        _invfac[m] = _fac[m].inv();
206

207
        for (int i = m; i > old; i--)
208
        {
209
            _invfac[i - 1] = _invfac[i] * i;
210
            _inv[i] = _invfac[i] * _fac[i - 1];
211
        }
212

213
        n = m;
214
    }
215

216
    Z fac(int m)
217
    {
218
        if (m > n)
219
            init(2 * m);
220
        return _fac[m];
221
    }
222

223
    Z invfac(int m)
224
    {
225
        if (m > n)
226
            init(2 * m);
227
        return _invfac[m];
228
    }
229

230
    Z inv(int m)
231
    {
232
        if (m > n)
233
            init(2 * m);
234
        return _inv[m];
235
    }
236

237
    Z binom(int n, int m)
238
    {
239
        if (m < 0 || m > n)
240
            return 0;
241
        return fac(n) * invfac(m) * invfac(n - m);
242
    }
243

244
    Z perm(int n, int m)
245
    {
246
        if (m < 0 || m > n)
247
            return 0;
248
        return fac(n) * invfac(n - m);
249
    }
250
} comb;
251

252
void solve()
253
{
254
    int x1, x2, x3;
255
    cin >> x1 >> x2 >> x3;
256

257
    comb.init(x1 + x2 + x3 + 5);
258

259
    if (x1 == 0)
260
    {
261
        cout << comb.binom(x2 + x3, x3) << endl;
262
        return;
263
    }
264
    if (x3 == 0)
265
    {
266
        cout << comb.binom(x1 + x2, x1) << endl;
267
        return;
268
    }
269

270
    Z res = 0;
271
    int lim = min(x1, x2 + 1);
272

273
    for (int k = 1; k <= lim; k++)
274
    {
275
        Z a = comb.binom(x2 + 1, k);
276
        Z b = comb.binom(x1 - 1, k - 1);
277
        Z c = comb.binom(x2 + x3 - k, x3);
278

279
        res += a * b * c;
280
    }
281

282
    cout << res << endl;
283
}
284

285
int main()
286
{
287
    fastio();
288

289
    int T = 1;
290
    // cin >> T;
291

292
    while (T--)
293
        solve();
294

295
    return 0;
296
}