第一次打d1！中间出了点小差错，以及被数据结构题目卡了一下，不过无伤大雅，没有掉分也没有涨分。
Div.2 B
题目大意：给定一个大小为 $n \times m$ 的矩阵，现在要求其中任意大小为 $r \times c$ 的矩阵，其中元素的异或和都需要为 $0$ ，问满足条件的 $01$ 矩阵有多少个？请求出数量并模 $998244353$ 。
数据范围： $1 \leq r \leq n \leq 10^9,1 \leq c \leq m \leq 10^9$
思路：这种题，很显然会想到滑窗类似物，或者实在不行你看着前几个样例可以打表。
这里来讲一下正经思路，首先考虑最左上角的一个矩形，假设左上角为 $(1,1)$ ，当其他的都固定之后， $(r,c)$ 可以直接算出来，再考虑旁边的矩形，如果固定 $(1,c+1)$ 到 $(r-1,c+1)$ ，那么 $(r,c+1)$ 也可以直接算出来，以此类推，得到需要固定的个数为 $n \times m - (n-r+1) \times (m-c+1)$ 个，然后用快速幂做即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| using i128 = __int128_t;
const ll MOD = 998244353;
ll mul(ll x, ll y) { return x * y % MOD; }
ll qpow(ll x, ll n) {
ll res = 1;
for (; n; n >>= 1) {
if (n % 2) res = res * x % MOD;
x = x * x % MOD;
}
return res;
}
void solve() {
ll n, m, r, c;
cin >> n >> m >> r >> c;
cout << qpow(2, n * m - (n - r + 1) * (m - c + 1)) << endl;
return;
}
|
Div.1 A
题目大意：Alice和Bob正在玩一个由 $n$ 个非负整数组成的数组 $a$ 的游戏，每轮游戏，当前玩家都需要选择一个数组 $b$ ，满足 $0 \leq b_i \leq a_i, \sum\limits_{i=1}^{n}b_i \neq 0,b_1 \bigoplus b_2 \ldots \bigoplus b_n=0$ ，然后使 $a_i=a_i-b_i$ ，现在Alice先手，请计算Alice在第一轮中为保证获胜而可选的数组 $b$ 的数量，并模 $998244353$ 。
数据范围： $1 \leq n \leq 10^6, 1 \leq \sum n \leq 10^6,1 \leq a_i < 2^{30}$
思路：之前有道题的思路特别深刻，也是博弈，就是强调Alice是否能一次就把Bob杀掉。
本题我们依旧从这个角度开始思考，不难想到，当一个玩家无法行动时，最后的情况是，显然剩下的 $a_i$ 要么都是 $0$ ，要么最多只能有一个正数。
于是，考虑alice第一步把Bob逼死的情况，结合样例发现是对的，但是检查这个运算符优先级检查了一会。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| using i128 = __int128_t;
const ll MOD = 998244353;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
if (n == 1) {
cout << 0 << endl;
return;
}
ll tot = 0;
rep(i, 0, n - 1) tot ^= a[i];
ll ans = (tot == 0);
rep(i, 0, n - 1) {
if ((tot ^ a[i]) < a[i]) ans++;
}
cout << ans << endl;
return;
}
|
Div.1 B
题目大意：有 $n$ 个人围成一圈，按顺时针编号为 $1 \sim n$ ，每个人都有一个值 $a_i$ 以及共同的视野范围 $d$ ，可以看到左边 $d$ 个人和右边 $d$ 个人（自己不能看见），每个人的幸福感由以下规则决定：如果他收到了礼物，且视野范围内有 $x$ 人没有收到礼物，他就能获得 $x \times a_i$ 的幸福感，如果他没收到礼物，且视野范围内有 $x$ 人收到礼物，他就能获得 $-x \times a_i$ 的幸福感，请计算合理安排礼物状况下，总的最大幸福感。
数据范围： $3 \leq n \leq 2 \cdot 10^5, 1 \leq d < \frac{n}{2},1 \leq a_i \leq 10^8$
思路：首先，看到题目的式子结构，很显然会想到用 $x_i$ 是 $0,1$ 来表示是否拿取自己的礼物，于是一个人的幸福感就可以表示为
$$
\left(2d x_i-\sum\limits_{j \in N(i)}x_j\right)a_i
$$于是有
$$
\begin{aligned}
\sum\limits_{i=1}^{n}\left(2d x_i-\sum\limits_{j \in N(i)}x_j\right)a_i
&=\sum\limits_{i=1}^{n}2d x_i a_i-\sum\limits_{i=1}^{n}a_i\sum\limits_{j \in N(i)}x_j \\\\
&=\sum\limits_{i=1}^{n}2d x_i a_i-\sum\limits_{i=1}^{n}x_i\sum\limits_{j \in N(i)}a_j \\\\
&=\sum\limits_{i=1}^{n}x_i\left(2d a_i-\sum\limits_{j \in N(i)}a_j\right)
\end{aligned}
$$然后用前缀和贪心即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| using i128 = __int128_t;
void solve() {
ll n, d;
cin >> n >> d;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) a.push_back(a[i]);
vl pre(2 * n);
pre[0] = a[0];
rep(i, 1, 2 * n - 1) pre[i] = pre[i - 1] + a[i];
ll ans = 0;
rep(i, 0, n - 1) {
ll tem = 2 * d * a[i] - (pre[i + d] - pre[i] + pre[i + n - 1] - pre[i + n - 1 - d]);
if (tem >= 0) ans += tem;
}
cout << ans << endl;
return;
}
|
Div.1 C
题目大意：对于 $1 \sim n$ 的排列 $p$ ，现在针对每个 $i \in [1,n]$ ，给出 $p_i$ 或 $s_i$ ，其中 $s_i$ 为前缀 $1 \sim i$ 中的逆序对数，请你还原出一个可能的排列，题目保证有解。
数据范围： $1 \leq n \leq 2 \cdot 10^5,1 \leq \sum n \leq 2 \cdot 10^5$
思路：由于题目的特殊性质，不难想到按照 $s$ 出现来分段处理，然后考虑贡献，这里一开始考虑的是正序遍历，然后没调出来，于是考虑倒序遍历。
假设当前要处理的 $s$ 位置是 $r$ ，而上一个给出 $s$ 的位置是 $l$ ，这里区间 $(l,r]$ 新增逆序对的贡献，可以用以下的思路来分类讨论。
首先，是 $(l,r)$ 这段已知的数构成的逆序对，然后是 $(l,r)$ 对于 $[1,l]$ 的逆序对，最后是 $r$ 对于 $[1,r)$ 的逆序对，然后由于 $p_r$ 是未知的，因此可以先假设所有去掉 $(l,r)$ 后剩下的数字都在 $[1,l]$ ，再二分确定 $p_r$ 具体是哪个数，优化使用一棵永久BIT来维护剩下没填的数，以及一棵临时BIT用于计算 $(l,r)$ 中的逆序对。
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
132
133
| using i128 = __int128_t;
template <typename T = long long>
class Tree {
vector<T> tree;
public:
// 构造函数：初始化大小为 n 的树状数组，初始所有元素值为 val（外部表现为 0-based）
Tree(int n, T val = 0) : tree(n + 1) {
for (int i = 1; i <= n; i++) {
tree[i] += val;
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
}
}
}
// 构造函数：使用给定的 vector 在 O(N) 时间内快速初始化建树
Tree(const vector<T>& data) {
int n = data.size();
tree.resize(n + 1);
for (int i = 1; i <= n; i++) {
tree[i] += data[i - 1]; // data是 0-based
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
}
}
}
// 单点修改：将 0-based 下标 i 处的元素增加 val
void add(int i, T val = 1) {
for (++i; i < tree.size(); i += i & (-i)) {
tree[i] += val;
}
}
// 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
T pre(int i) const {
T res = 0;
for (++i; i > 0; i &= i - 1) {
res += tree[i];
}
return res;
}
// 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
T query(int l, int r) const {
if (r < l) {
return 0;
}
return pre(r) - pre(l - 1); // 当 l=0 时, pre(-1) 会合理地返回 0
}
// 树上二分查找：返回满足前缀和 >= val 的最小 0-based 下标
int lower_bound(T val) const {
int w = bit_width(tree.size() - 1);
int res = 0;
T s = 0;
for (int i = w - 1; i >= 0; i--) {
int nxt = res + (1 << i);
if (nxt < tree.size() && tree[nxt] + s < val) {
res += (1 << i);
s += tree[nxt];
}
}
return res; // 返回 0-based 下标：内部 1-based 下标为 res + 1，因此 0-based 为 res
}
};
void solve() {
ll n, x;
char op;
cin >> n;
vl a(n, -1);
vl b(n, -1);
vl pos;
Tree tree1(n, 1);
Tree tem(n);
rep(i, 0, n - 1) {
cin >> op >> x;
if (op == 'p') {
a[i] = x - 1;
} else {
b[i] = x;
pos.push_back(i);
}
}
if (sz(pos) == 0) {
rep(i, 0, n - 1) cout << a[i] + 1 << ' ';
cout << endl;
return;
}
vl res(n, -1);
rep(i, 0, n - 1) {
if (a[i] != -1) res[i] = a[i];
}
int m = sz(pos);
int cnt = m - 1;
frep(i, n - 1, pos[m - 1] + 1) tree1.add(a[i], -1);
frep(i, m - 1, 0) {
ll r = pos[i], l = (i == 0 ? -1 : pos[i - 1]);
ll re = b[pos[i]] - (i == 0 ? 0 : b[pos[i - 1]]);
vl tem3;
frep(j, r - 1, l + 1) {
re -= tree1.query(a[j] + 1, n - 1);
tree1.add(a[j], -1);
tem.add(a[j], 1);
tem3.push_back(a[j]);
}
ll tot = tree1.query(0, n - 1);
ll l1 = 1, r1 = tot, mid, ans = 1;
auto check = [&](ll mid) -> bool {
ll tem2 = tree1.lower_bound(mid);
ll re2 = tree1.query(tem2 + 1, n - 1) + tem.query(tem2 + 1, n - 1) - tem.query(0, tem2 - 1);
return re2 >= re;
};
while (l1 <= r1) {
mid = (l1 + r1) / 2;
if (check(mid)) {
ans = mid;
l1 = mid + 1;
} else
r1 = mid - 1;
}
ll tem2 = tree1.lower_bound(ans);
tree1.add(tem2, -1);
res[r] = tem2;
for (auto& p : tem3) tem.add(p, -1);
}
rep(i, 0, n - 1) cout << res[i] + 1 << ' ';
cout << endl;
return;
}
|
Div.1 D
题目大意：给定 $n$ 个点，称一个图为功能图，当且仅当这 $n$ 个点之间有 $n$ 条有向边，并且没有自环，每个图的贡献为选定 $m$ 个点，能从这 $m$ 个点到达整个图的点集数，现在请求出所有功能图的贡献之和，并模 $998244353$ 。
数据范围： $1 \leq m \leq n \leq 10^6,1 \leq \sum n \leq 10^6$
思路：首先考虑到，可以从点集的角度来衡量贡献，也就是针对任意的点集，计算能从它遍历到全图的功能图数，同时由于所有点集都是对称的，所以最后乘上一个
$$
\dbinom{n}{m}
$$即可。
然后就不会了，翻看评论区，发现了一种很妙的思路。
先将状态转化为
$$
(s,r)
$$这里 $s$ 表示为已经被访问过，但是没有确定出边的点， $r$ 为未被访问过的点，于是有两种操作，一种是
$$
(s,r) \rightarrow (s,r-1)
$$也就是访问了一个新点，贡献为 $r$ ，一种是
$$
(s,r) \rightarrow (s-1,r)
$$也就是接上了一个旧点，贡献为 $n-r-1$ 。
由题中所述，不难看出我们需要将
$$
(m,n-m)
$$转化为
$$
(0,0)
$$也就是需要有 $n-m$ 步访问新点，以及 $m$ 步的连接旧点，这里发现到，最后一步一定是
$$
(1,0) \rightarrow (0,0)
$$从而直接乘上一个 $n-1$ ，再考虑别的。
然后，所有发现新点的操作，其贡献依次是
$$
(n-m)(n-m-1) \cdots 1=(n-m)!
$$现在只需要考虑安排剩下的 $m-1$ 次指向旧点，由于每次不能指向自己，因此还有 $r$ 个点未访问时，指向旧点的贡献为 $n-r-1$ 。
于是得到固定点集的方案数为
$$
F=(n-1)(n-m)!\sum\limits_{a_0+\ldots+a_{n-m}=m-1}\prod\limits_{r=0}^{n-m}(n-r-1)^{a_r}
$$然后，后面这坨怎么算？考虑到
$$
\sum\limits_{a_0+\ldots+a_{n-m}=m-1}\prod\limits_{r=0}^{n-m}(n-r-1)^{a_r}
=[x^{m-1}]\prod\limits_{r=0}^{n-m}\frac{1}{1-(n-r-1)x}
$$接着由于有标准恒等式
$$
[z^d]\prod\limits_{r=0}^{k}\frac{1}{1-x_rz}
=\sum\limits_{i=0}^{k}\frac{x_i^{d+k}}{\prod\limits_{j \neq i}(x_i-x_j)}
$$代回原来式子，得到
$$
\prod\limits_{j \neq i}(x_i-x_j)
=\prod\limits_{j \neq i}(j-i)
=(-1)^i i!(k-i)!
$$于是有
$$
\begin{aligned}
F
&=(n-1)(n-m)!\sum\limits_{i=0}^{n-m}(-1)^i\frac{(n-i-1)^{n-1}}{i!(n-m-i)!} \\\\
&=(n-1)\sum\limits_{i=0}^{n-m}(-1)^i\dbinom{n-m}{i}(n-i-1)^{n-1}
\end{aligned}
$$最后使用快速幂等等求解即可。
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
| using i128 = __int128_t;
const ll MOD = 998244353;
constexpr int MX = 1e7 + 1;
ll F[MX]; // 预处理阶乘
ll INV_F[MX]; // 预处理逆元
ll mul(ll x, ll y) { return x * y % MOD; }
ll qpow(ll x, int n) {
ll res = 1;
for (; n; n >>= 1) {
if (n % 2) res = res * x % MOD;
x = x * x % MOD;
}
return res;
}
auto init = [] {
F[0] = 1;
for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % MOD; // 预处理阶乘
INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
for (int i = MX - 1; i; i--) {
INV_F[i - 1] = INV_F[i] * i % MOD;
} // 预处理逆元
return 0;
}();
// 计算C(n,m),即从n个数中取m个数
ll comb(int n, int m) { return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD; }
void solve() {
ll n, m;
cin >> n >> m;
ll ans = 0;
rep(i, 0, n - m) {
if (i % 2 == 0)
ans = (ans + mul(comb(n - m, i), qpow(n - i - 1, n - 1))) % MOD;
else
ans = (ans - mul(comb(n - m, i), qpow(n - i - 1, n - 1)) + MOD) % MOD;
}
cout << mul(ans, mul((n - 1), comb(n, m))) << endl;
return;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
|
