XXI Open Cup, Grand Prix of Belarus 2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest 题解( 二 ) _生活百科

\[\frac{(2n)!}{n!*2^n} = \frac{\begin{pmatrix} 2n\\n\end{pmatrix} * n!}{2^n}\]然后每个组合其实可以看成是一个点，然后有一个重要的结论，$n$ 个点的生成树个数为 $n^{n-2}$ 个。然后由于每个最后连的边，具体到这道题里都是四条，所以最后还要乘上 $4^{n - 2}$
所以最后的公式就是
\[\frac{\begin{pmatrix} 2n\\n\end{pmatrix}*n!}{2^n}*4^{n-1}*n^{n-2}\]

Code

#include<bits/stdc++.h>#define debug(x) cerr << #x << " = " << x << '\n';using namespace std;typedef long long ll;#define int llconst int inf = 0x3f3f3f3f;const ll mod = 998244353;const int N = 1e6 + 10;int fac[N], inv[N];ll ksm(ll a, ll b) {ll ans = 1;while (b) {if (b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}ll c(ll k, ll n) {return fac[n] % mod * inv[k] % mod * inv[n - k] % mod;}void solve() {int n;cin >> n;if (n & 1) {cout << 0 << '\n';return;}if (n == 2) {cout << 1 << '\n';return;}int k = n / 2;ll ans = c(k, n) * fac[k] % mod;for (int i = 1; i <= k; ++i) {ans = ans * ksm(2, mod - 2) % mod;}for (int i = 1; i <= k - 1; ++i) {ans = ans * 4 % mod;}cout << ans * ksm(k, k - 2) % mod << '\n';}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int t = 1;// cin >> t;fac[0] = inv[0] = 1;for (int i = 1; i <= 1e6; ++i) {fac[i] = fac[i - 1] * i % mod;inv[i] = ksm(fac[i], mod - 2) % mod;}while(t--) {solve();}return 0;}

I. Binary Supersonic Utahraptors题意：略

Solution答案恒定不变，签到题

Code

int n,m,k;void solve() {int cnt_y=0,cnt_r=0;cin>>n>>m>>k;for(int i=1,x;i<=n;++i){cin>>x;cnt_y+=(x==0);}for(int i=1,x;i<=m;++i){cin>>x;cnt_r+=(x>0);}cout<

J. Burnished Security Updates题意：略

Solution考虑二分图染色（签到题）

Code

const int maxn = 3e5 + 100, mod = 1e9 + 7;int n, m, cnt, sz, col[maxn], ok = 1;vector e[maxn];void dfs(int u, int fa, int co) {col[u] = co;if (co == 1) cnt++;sz++;for (int v: e[u]) {if (v == fa) continue;if (col[v] == col[u]) {ok = 0;return;}if (!col[v]) dfs(v, u, -co);}}int main() {cin >> n >> m;for (int i = 1; i <= m; i++) {int u, v;cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}int ans = 0;for (int i = 1; i <= n; i++) {if (!col[i]) {cnt = sz = 0;dfs(i, 0, 1);if (!ok) {cout << -1;return 0;}ans += min(sz - cnt, cnt);}}cout << ans;}

M. Brilliant Sequence of Umbrellas构造一个长度至少为 $\left \lceil \frac{2}{3}\sqrt{n}\right \rceil $ 的递增数组，使得两两做 $gcd$ 也是递增的。

Solution由于 $gcd$ 的数组也是递增的，那么要让数组尽可能的长，就要让 $gcd$ 增长的尽可能慢。
通过打表前面几个数
\[1 \ 2 \ 6 \ 15 \ 35 \ 56 \ 72 \ 99 \\gcd数组:2 \ 3 \ 5 \ 7 \ 8 \ 9 \ 11\]可以发现 $gcd$ 数组要添加的数，应当是与最后一个和倒数第二个都互质的数，然后原数组就是 $gcd$ 数组相乘回去

Code

typedef long long ll;const int mod = 998244353;const int N = 1e5 + 10;vector a{1, 2, 6}, g{1, 2, 3};void solve() {ll n;cin >> n;ll k = ceil(2 * sqrt(n) * 1.0 / 3);int cnt = 0;for (int i = 0; i < a.size(); ++i) {if (a[i] <= n) cnt++;if (cnt >= k) break;}if (cnt >= k) {cout << k << '\n';for (int i = 0; i < k; ++i) {cout << a[i] << " \n"[i == k - 1];}} else {cout << "-1\n";}}int main() {ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int t = 1;for (int i = 4; i <= 1e6; ++i) {if (__gcd(g.back(), i) == 1 $&&$ __gcd(g[g.size() - 2], i) == 1) {if (g.back() * i <= 1e12) a.push_back(g.back() * i), g.push_back(i);else break;}}while (t--) {solve();}return 0;}

N. Best Solution Unknown$n$个数，总共进行$n-1$次操作。每次操作选两个相邻的数，删去较小值，若两数相等，则任意删除其一，留下的数增大$1$ 。问最后有可能剩下的数有哪些，按升序输出下标。每次随机取比赛，求会有哪些人可能赢