C. Jiaxun!
开局一眼顶针，二分答案，怒写暴力，爽吃罚时，遗憾下机。
队长深思之后，发现三个点之间互相开通道，流量固定即可。
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int s;
cin >> s;
vector<int> a(8);
for (int i = 1; i <= 7; i++) cin >> a[i];
auto check = [&](int x) {
ll cnt[4] = {0};
cnt[1] = a[1] + a[3];
cnt[2] = a[2] + a[6];
cnt[3] = a[4] + a[5];
ll b3 = a[3], b6 = a[6], b5 = a[5];
int t = 100;
while (t--) {
if (cnt[1] > x) {
ll mv = min((ll)cnt[1] - x, b3);
cnt[1] -= mv;
cnt[2] += mv;
b3 -= mv;
}
if (cnt[2] > x) {
ll mv = min((ll)cnt[2] - x, b6);
cnt[2] -= mv;
cnt[3] += mv;
b6 -= mv;
}
if (cnt[3] > x) {
ll mv = min((ll)cnt[3] - x, b5);
cnt[3] -= mv;
cnt[1] += mv;
b5 -= mv;
}
}
ll res = 0;
for (int i = 1; i <= 3; i++) res += max(0LL, x - cnt[i]);
return res <= a[7];
};
int l = 0, r = s, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
D. Arcane Behemoths
显然，数组排序后，从大到小删元素。
接着考虑排列组合可以得到公式：
$$\sum_{x=0}^{n-1} \binom{n-i}{x} \left[ \underbrace{\binom{i-1}{0}}_{y=0} a_i + \sum_{y=1}^{i-1} \binom{i-1}{y} a_i 2^{y-1} \right]$$$$\sum_{y=0}^{i-1} \binom{i-1}{y} 2^y = \mathbf{3}^{i-1}$$得到最终式：
$$\sum_{x=0}^{n-1} \binom{n-i}{x} \sum_{y=0}^{i-1} \binom{i-1}{y} a_i 2^{y-1} = a_i 2^{n-i} \frac{3^{i-1}+1}{2}$$
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 998244353;
ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void solve() {
int n;
cin >> n;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a.begin() + 1, a.end());
ll ans = 0;
for (int i = 1; i <= n; i++) {
ll res = a[i];
res = (res * qpow(2, n - i) % mod) % mod;
res = (res * (qpow(3, i - 1) + 1) % mod * qpow(2, mod - 2) % mod) % mod;
ans = (ans + res) % mod;
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
E. Zero
打表发现，奇数 i 位都是 $(2^m - 1)^i$，将此规律套到偶数位，会发现，偶数 i 位会差 $(1 - 2^m)^{n/2}$
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 998244353;
ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void solve() {
int n, m;
cin >> n >> m;
ll ans = qpow((qpow(2, m) - 1 + mod) % mod, n - 1);
if (!(n & 1)) ans = (ans + mod + qpow(1 - qpow(2, m), n / 2)) % mod;
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
H. Tree Shuffling
首先一次操作的作用是选择一条链并随意打乱链上的点权。
首先单独计数计数序列 $a_i = i$。
对于一个最终得到的点权序列 $a_1, a_2, \cdots, a_n$，其可以构造的条件为满足 $a_i \neq i$ 的点位于一条链上。
从链的角度出发计数，为了保证不重复计数，我们希望对于序列 $a_1, a_2, \cdots, a_n$，只在最短的可行链处计数。
对于一条长度为 $k$ 的链，有 $k!$ 种不同的打乱链的方式。假设其左右两端点分别为 $x, y$，则如果 $a_x = x$ 或者 $a_y = y$时，可以操作更短的链得到序列，于是我们减去这两种情况，即 $2(k-1)!$。然而此时 $a_x = x$ 且 $a_y = y$ 的序列会被重复减，再加回去 $(k-2)!$ 即可。
注意到上述计数只与链的长度有关，于是只需要统计出每种长度的链分别有多少条即可，这个用从每个点出发遍历就可以 $O(n^2)$。
（来源：
QOJ
）
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e4 + 7, mod = 998244353;
ll fact[N];
ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void init() {
fact[0] = 1;
for (int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % mod;
}
void solve() {
int n;
cin >> n;
vector<int> g[n + 1], dep(n + 1);
vector<vector<int>> fa(n + 1, vector<int>(20));
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
function<void(int, int)> dfs = [&](int u, int Fa) {
fa[u][0] = Fa;
for (int i = 1; i < 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (auto v : g[u]) {
if (v == Fa) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
}
};
dfs(1, 0);
auto lca = [&](int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int d = dep[x] - dep[y];
for (int i = 19; i >= 0; i--) if (d >> i & 1) x = fa[x][i];
if (x == y) return x;
for (int i = 19; i >= 0; i--) {
if (fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
};
auto dist = [&](int x, int y) {
int z = lca(x, y);
return dep[x] + dep[y] - 2 * dep[z];
};
ll ans = 1;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
int k = dist(i, j) + 1;
if (k >= 2) {
ll f = (fact[k] - 2 * fact[k - 1] % mod + fact[k - 2]) % mod;
if (f < 0) f += mod;
ans = (ans + f) % mod;
}
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init();
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
I. DAG Query
赛时想到解多项式，平时没写过，难顶。
问 $f(1, n, c)$ 999 次，$c->(1, 999)$。
可以得到关于 $x, x^2, x^3, …, x^999$ 的关系式。
用高斯消元求解各系数即可。
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
|
#include <bits/stdc++.h>
using namespace std;
// #define endl "\n"
typedef long long ll;
const int N = 1e3 + 7, mod = 998244353;
ll a[N][N], ans[N];
int n, m;
ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int gauss(int n) {
for (int i = 0; i < n; ++i) ans[i] = 0;
int r = 0;
for (int c = 0; c < n; ++c) {
if (r == n) break;
int p = r;
while (p < n && a[p][c] == 0) ++p;
if (p == n) continue;
for (int i = c; i <= n; ++i) swap(a[r][i], a[p][i]);
ll inv = qpow(a[r][c], mod - 2);
for (int i = c; i <= n; ++i) a[r][i] = a[r][i] * inv % mod;
for (int i = 0; i < n; ++i) if (i != r && a[i][c]) {
ll fact = a[i][c];
for (int j = c; j <= n; ++j) {
a[i][j] = (a[i][j] - fact * a[r][j]) % mod;
if (a[i][j] < 0) a[i][j] += mod;
}
}
++r;
}
if (r < n) {
for (int i = r; i < n; ++i) if (a[i][n]) return 2;
return 1;
}
for (int i = 0; i < n; ++i) ans[i] = a[i][n];
return 0;
}
ll query(int x) {
cout << "? 1 " << n << " " << x << endl;
ll res;
cin >> res;
return res;
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
}
for (int i = 0; i < n - 1; i++) {
ll y = query(i + 1);
ll now = 1;
for (int j = 0; j < n - 1; j++) {
now = now * (i + 1) % mod;
a[i][j] = now;
}
a[i][n - 1] = y;
}
gauss(n - 1);
cout << "!" << endl;
int k;
cin >> k;
ll res = 0;
for (int i = 0; i < n - 1; i++) {
res = (res + ans[i] * qpow(k, i + 1)) % mod;
}
cout << res << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
|