The 2025 ICPC Asia East Continent Online Contest (II)(C,D,E,H,I)

C. Jiaxun!

C思路

首先来了解一下 \(Hall\) 定理，对于二分图 \(G<X+Y, M>\) （ \(X\) 表示左边点集，\(Y\) 表示右边点集，\(M\) 表示边集），令 \(W\) 表示 \(X\) 的子集， \(N(W)\) 表示 \(W\) 邻居的点集，则有

\[|W|\; \leq \; |N(W)| \]

如果对于其所有子集都成立，那么我们认为图 \(G\) 有完备匹配。

本题用到的还有推论,若所有的子集 \(W\) 满足:

\[k|W|\; \leq \; |N(W)| \]

则每个左点集的点均可以同时匹配 \(k\) 个右点。

Hall定理的证明, 想了解证明的可以走这里。

很好，那这道题怎么用的呢，首先我们将三人定义为左点集，七道题目定义为右点集。但在这里右点集是存在点权的，利用到一个经典思想拆点。

比如说一个权值为 \(v\), 连接边的情况是 \(e\) 的点，我们将其拆为 \(v\) 个权值为 \(1\), 连接边的情况均为 \(e\) 的点。

然后我们认为每个人有 \(s\) 个完美匹配是每个人最少要做 \(s\) 的任务。

我们此时只需要二分每个人最少要做多少任务，\(check\) 是 \(O(7*7)\) 的时间复杂度，总复杂度为 \(O(T \log S)\).

C代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;const ll mod = 998244353;void solve(){ll n;cin >> n;vector<ll> a(8);for(ll i = 1; i <= 7; i++ ){cin >> a[i];}auto check = [&](ll mid){for(ll i = 1; i < 8; i++){ll num = __popcount(i);ll sum = 0;for(ll j = 1; j < 8; j++){if((i & j) > 0){sum += a[j];}}      // cout << sum << " " << mid * num << " " << mid << " " << num << "\n";if(sum < mid * num)return false;}return true;};ll l = 1;ll r = 1e9;ll flag = 0;while(l <= r){ll mid = (l + r) / 2;if(!check(mid)){r = mid - 1;}else l = mid + 1;} cout << r << "\n";
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();return 0;
}

D. Arcane Behemoths

D思路

我们分开计算每个 \(a_i\) 的贡献，\(a_i\) 的贡献分为在子序列中比 \(a_i\) 小的部分和比 \(a_i\) 大的部分。

先排序，比 \(a_i\) 小的数有 \(i - 1\) 个，比 \(a_i\) 大的数有 \(n - i\) 个。

先考虑 \(a_i\) 是最大值的情况，也是子序列中仅包含前 \(i\)个元素，当子序列元素数量为 \(j\) 时, 贡献为 \({i - 1 \choose j}\,* \, 2^{j - 1} * a_i\)。

当 \(a_i\) 是子序列最大值时，所有的情况 的贡献为 \((\sum_{j = 1}^{i - 1}\,{i - 1 \choose j}\,* \, 2^{j - 1}\;+\;1) * a_i\)。

转换一下形式就是 \(1/2 * (\sum_{j = 0}^{i - 1}\,{i - 1 \choose j}\,* \, 2^j\;+\;1)* a_i\), 也就是 \(1/2 * ((2 + 1)^{i - 1} + 1) * a_i\)。

对于大于 \(a_i\) 的后面 \(n - i\) 个元素，共有 \(2^{n - i}\) 种选法。

所以第 \(i\) 个值的贡献是 \(1/2 * (3^{i - 1} + 1) * 2^{n - i} * a_i\), 累加求和即可。

D代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;const ll mod = 998244353;void solve(){ll n;cin >> n;vector<ll> a(n + 1);for(ll i = 1; i <= n; i++){cin >> a[i];}sort(a.begin() + 1, a.end());auto qpow = [&](ll a, ll b){ll res = 1;while(b){if(b & 1){res = res * a % mod;}a = a * a % mod;b /= 2;}return res;};ll ans = 0;for(ll i = 1; i <= n; i++){ans = (ans + (qpow(3, i - 1) + 1) % mod * qpow(2, mod - 2) % mod * a[i] % mod * qpow(2, n - i)) % mod;}cout << ans << "\n";
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();return 0;
}

E. Zero

E思路

定义 \(k\) 为 \(2^m\).

要让 \(n\) 个数的异或和为 \(0\), 前 \(n - 1\) 个数相邻不重的任意选，第 \(n\) 个数选择前 \(n - i\) 个数的异或和，这样选的结果一定是 \(0\)。

选法方案数是 \(f_n = k * (k - 1) ^ {n - 2}\)。

但这还存在问题，如果前 \(f_{n - 2}\) 个数的异或和为 \(0\), 这时，第 \(n - 1\) 和 \(n\) 个数就会选择一样的数，导致方案不合法，所以这里还需要减去不合法的方案，也就是

\[f_n = k * (k - 1) ^ {n - 2} - (k - 1) * f_{n - 2} \]

\(O(n)\)求这个式子会超时，不可取。（可以左右累乘求通项）

考虑写成矩阵形式

\[\left[\begin{matrix}f_n\\f_{n - 2}\\k*(k - 1)^n\\\end{matrix} \right]= \left[\begin{matrix}-(k-1) & 0 & 1 \\1 & 0 & 0\\0 & 0 & (k - 1)^2\\\end{matrix} \right] \left[\begin{matrix}f_{n - 2}\\f_{n - 4}\\k*(k - 1)^{n - 2}\\\end{matrix} \right]\]

运用矩阵快速幂即可用 \(\log\) 的复杂度解决了。

E代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;const ll mod = 998244353;void solve(){int n, m;cin >> n >> m;auto qpow = [&](ll a, ll b){ll res = 1;while(b){if(b & 1){res = res * a % mod;}a = a * a % mod;b /= 2;}return res;};ll k = qpow(2, m);auto add = [&](vector<vector<ll>> a, vector<vector<ll>> b){vector<vector<ll>> res(a.size(), vector<ll> (b[0].size()));for(int i = 0; i < a.size(); i++){for(int j = 0; j < b[i].size(); j++){for(int k = 0; k < b.size(); k++){res[i][j] = (res[i][j] + a[i][k] * b[k][j] % mod) % mod; }}}return res;};auto qp = [&](vector<vector<ll>> a, ll b){vector<vector<ll>> res(3, vector<ll> (3));for(int i = 0; i < 3; i++){res[i][i] = 1;}while(b){if(b & 1){res = add(res, a);}a = add(a, a);b /= 2;}return res;};vector<ll> ans(7);//奇数时起点ans[1] = (k - 1) * (k - 1) % mod;//f_3ans[2] = 1;//f_1ans[3] = k * (k - 1) % mod * ans[1] % mod;// n - 2 == 3//偶数时起点ans[4] = ans[1] * k % mod;//f_4ans[5] = 0;//f_2ans[6] = k * ans[1] % mod * ans[1] % mod;//n - 2 == 4vector<vector<ll>> a = {{(1 - k + mod) %mod, 0, 1}, {1, 0, 0}, {0, 0, ans[1]}};if(n == 1){cout << ans[2] << "\n"; }else if(n == 2){cout << ans[5] << "\n"; }else if(n == 3){cout << ans[1] << "\n"; }else if(n == 4){cout << ans[4] << "\n"; }else if(n % 2 == 1){a = qp(a, (n - 3)/2);//最开始n - 2 == 3ll res = (a[0][0] * ans[1] % mod + a[0][1] * ans[2] % mod + a[0][2] * ans[3]  % mod) % mod;cout << res << "\n";}else{a = qp(a, (n - 4)/2);//最开始n - 2 == 4ll res = (a[0][0] * ans[4] % mod + a[0][1] * ans[5] % mod + a[0][2] * ans[6] % mod) % mod;cout << res << "\n";}}int main(){ios::sync_with_stdio(0);cin.tie(0);int t;cin >> t;while(t--)solve();return 0;
}

H. Tree Shuffling

H思路

枚举链的两端，确保两端都不在自己原来的位置上即可。

发现会算重，考虑容斥。\(ans = n! - 2*(n - 1)! + (n - 2)!\), 其中 \(n\) 表示两点间距离。

H代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
void solve(){ ll n;cin >> n;vector<vector<ll>> e(n + 1);vector<ll> d(n + 1);vector<ll> f(n + 1);f[0] = 1;for(ll i = 1; i <= n; i++){f[i] = f[i - 1] * i % mod;}for(ll i = 1; i < n; i++){ll x, y;cin >> x >> y;e[x].push_back(y);e[y].push_back(x);}auto dfs = [&](auto&& dfs, ll u, ll fa) -> void {// cout << u << endl;for(auto v : e[u]){if(v == fa)continue;d[v] = d[u] + 1;dfs(dfs, v, u);}};ll ans = 0;for(ll i = 1; i <= n; i++){for(ll j = 1; j <= n; j++)d[j] = 0;dfs(dfs, i, 0);for(ll j = i + 1; j <= n; j++){// if(i == j)continue;ans = (ans + f[d[j] + 1] - 2 * f[d[j]] + 2 * mod + f[d[j] - 1]) % mod;}// cout << "aaaaaaaaaaaa" << endl;}cout << (ans + 1) % mod << "\n";
}   int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while(t--){solve();}
}

I. DAG Query

I思路

对于 \(1\) 到 \(n\) 的很多走法中，共有至多 \(999\) 项未知数，分别是 \(a_1 c^1, a_2 c^2, ..., a_999 c^999\),通过 \(999\) 次询问，我们可以建立 \(1000\) 个键值对（包括\(（0,0）\)），通过插值的方式来求解，得到答案。

或者说这是 \(999\) 的多项式，所以插值 \(999\) 次后，答案准确。

I代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
void solve(){ ll n, m;cin >> n >> m;for(ll i = 1; i <= m; i++){ll a, b;cin >> a >> b;}vector<ll> x(1000);vector<ll> y(1000);for(ll i = 1; i <= 999; i ++){x[i] = i * 998000;cout << "? " << 1 << " " << n << " " << x[i] << endl;cin >> y[i];}cout << "!" << endl;ll k;cin >> k;auto qpow = [&](ll a, ll b){ll res = 1;while(b){if(b & 1){res = res * a % mod;}a = a * a % mod;b /= 2;}return res;};ll ans = 0;for(ll i = 0; i <= 999; i++){ll sum = y[i];for(ll  j = 0; j <= 999; j++){if(i == j)continue;sum = sum *  (k - x[j]) % mod * (qpow(x[i] - x[j], mod - 2)) % mod;}ans = (ans + sum + mod) % mod;}cout << ans << endl;
}   int main() {ios::sync_with_stdio(false);cin.tie(nullptr);// ll t;// cin >> t;// while(t--)solve();}