Educational Codeforces Round 142 (Rated for Div. 2)

A. GamingForces

每次打两个的技能只对两个 \(1\) 有效。

1
2
3
int n = rd(), cnt = 0;
for (int i = 1; i <= n; ++i) cnt += (rd() == 1);
printf("%d\n", n - cnt + cnt / 2 + cnt % 2);

B. Stand-up Comedian

先 a 再轮流 bc 最后 d 。

1
2
3
int a = rd(), b = rd(), c = rd(), d = rd();
if (b < c) swap(b, c);
printf("%d\n", a ? a + c * 2 + min(a + 1, b - c + d) : 1);

C. Min Max Sort

一个排列,每次可以选两个数 \(x,y\) ,将两者较小的移到开头,较大的移到结尾。

问排成增序所需最小操作次数。

倒着考虑,如果最后结束的时候开头不是 \(1\) ,结尾不是 \(n\) ,就一定要选一次 \((1, n)\)

以此类推,每次把最小和最大两个数删除,直到剩余序列是排序好的为止。懒删除复杂度 \(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define N 200007 
int a[N];
bool vis[N];
inline void work() {
int n = rd();
for (int i = 1; i <= n; ++i) {vis[i] = false; a[i] = rd();}
int ans = 0;
for (int i = 1, l = 1, r = n; l < r; ++i) {
while (vis[a[l]]) ++l;
while (vis[a[r]]) --r;
if (l >= r) break;
if (a[l] != i || a[r] != n - i + 1) ans = i;
vis[i] = vis[n - i + 1] = true;
}
printf("%d\n", ans);
}

D. Fixed Prefix Permutations

反演一下,考虑 \(a_j\) 能对每个 \(a_i\) 产生多少贡献,容易发现是 \(a_j\) 的逆和 \(a_i\) 的最长公共前缀。

把所有 \(a_j\) 的逆建一棵 Trie ,然后答案就是 \(a_i\) 在 Trie 上能跑到的最深的深度。复杂度 \(O(nm)\)

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define T int
typedef pair<T, T> pii;
typedef tuple<T, T, T> tii;

#define fr first
#define sc second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()

inline T rd() {
T x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

int n, m, tot;

struct node {
int son[10];
void clear() {for (int i = 0; i < 10; ++i) son[i] = 0;}
} c[1000007];

inline void insert(vector<int> &s) { // build trie
int rt = 0;
for (int j = 0; j < m; ++j) {
if (!c[rt].son[s[j]]) c[rt].son[s[j]] = ++tot;
rt = c[rt].son[s[j]];
}
}

inline int search(vector<int> &s) { // find the max depth s could reach
int rt = 0;
for (int j = 0; j < m; ++j) {
if (!c[rt].son[s[j]]) return j;
rt = c[rt].son[s[j]];
}
return m;
}

vector<int> a[50007], rev;

inline void work() {
n = rd(); m = rd(); rev.resize(m);
for (int i = 0; i < n; ++i) {
a[i].clear();
for (int j = 0; j < m; ++j) {
int x = rd() - 1;
rev[x] = j; a[i].push_back(x);
}
insert(rev);
}
for (int i = 0; i < n; ++i) printf("%d ", search(a[i]));
puts("");
for (int i = 0; i <= tot; ++i) c[i].clear();
tot = 0;
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}

E. Divisors and Table

给定 \(m_1, m_2\ (m_1,m_2\le 10^9)\) ,问 \(m_1\times m_2\) 有多少个因子出现在了 \(n\times n\) 的乘法表里。

此外,对于所有出现因子,求出来该因子出现的最小的行数。输出这些行数的异或和。

\(m_1m_2\le 10^{18}\) ,至多 \(10^6\) 个因子,\(15\) 个质因子,分开给的目的应该是不用 pollard rho。

那么对于每个因子 \(x\) ,保证列合法,找到其不超过 \(n\) 的最大的因子 \(y\) ,那么最小的行就是 \(x/y\)

假设这样的 \(y\)\(mx[x]\) ,使用搜索的方法生成因子 \(x\) ,那么 \(mx[x]\) 这个数组是可以递推的。

(对于某个 \(x\)\(x\) 包含的质因子 \(p_i\)\(mx[x]\) 可能的来源只有 \(mx[x/p_i]\)\(mx[x/p_i] * p_i\)

搜索的计算量是 \(\sum_{x|m_1m_2}\) \(x\) 的质因子个数,因此不会超过 \(15\times 10^6\) 可以接受。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define T int
typedef pair<T, T> pii;
typedef tuple<T, T, T> tii;

#define fr first
#define sc second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()

inline T rd() {
T x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 5007

vector<int> d, fac; // fac : prime factors of nw

vector<pii> s; // prime factors of m1m2

unordered_map<ll, ll> mx; // maximum divisor <= n

int n, tot, ans;

void dfs(ll nw, int step) {
if (step == s.size()) return;
dfs(nw, step + 1);
auto [p, t] = s[step];
fac.push_back(p);
for (; t; --t) {
nw *= p;
for (auto x : fac) {
ll y = mx[nw / x];
mx[nw] = max(mx[nw], (y * x <= n ? y * x : y));
}
if (nw / mx[nw] <= n) {++tot; ans ^= nw / mx[nw];}
else break;
dfs(nw, step + 1);
}
fac.pop_back();
}

inline void work() {
n = rd();
mx.clear(); d.clear(); s.clear();
mx[1] = 1; tot = ans = 1;

auto getd = [&](int x) {
int lim = sqrt(x);
for (int i = 2; i <= lim && i <= x; ++i)
while (x % i == 0) {d.pb(i); x /= i;}
if (x > 1) d.pb(x);
};
getd(rd()); getd(rd()); sort(all(d));

int lst = 0, cnt = 0;
for (auto x : d)
if (x != lst) {
if (lst) s.eb(lst, cnt);
lst = x; cnt = 1;
} else ++cnt;
s.eb(lst, cnt);

dfs(1, 0);
printf("%d %d\n", tot, ans);
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}

F. Graph Coloring

\(n\) 个点的完全图的边红蓝染色,求染色方案数模 \(998244353\) ,满足:

  • 至少有一条红边,至少有一条蓝边
  • 对于任何一个大于 \(2\) 的点集,其导出子图是红连通或蓝连通的,但不同时成立。

结论:若一幅图不连通,则其补图连通。

归纳证明,首先 \(1\) 个点的时候成立。假设 \(k\) 个点成立,那么对于新增的一个点:

  • \(k\) 个点都连通,那么图中该点连通了所有点。
  • \(k\) 个点都不连通,那么补图中该点连通了所有点。
  • 与一些点有边一些点无边,则原图连通即可连上该点,原图不连通则补图即可连上该点。

所以计数时只需要保证红蓝不同时连通即可。

假设 \(n\) 个点的答案为 \(A_n\) ,对于任意一个解边颜色取反仍然是一个解。

因此我们计数 \(n\) 个点,全集只被蓝色连通的方案数 \(B_n\) ,有 \(A_n=2\times B_n\) (特殊 \(A_1=B_1=1\) )。

递推考虑 \(1\) 号点被加入的情况。

对于 \(1\) 号点所在的红色连通分量(极大),由定义每个点和分量外的点的边都是蓝色。

这时想要把 \(1\) 号点蓝连通加入,则必定要选分量内的点和分量外的点的边。

无论分量外的点之间的边如何染色,这幅图的生成树必定包含蓝色的边,由开始的结论这幅图只能是蓝连通。

因此递推枚举红色连通分量的大小 \(k\) ,则分量内方案数 \(B_k\) ,分量外方案数 \(A_{n-k}\) ,有: \[ B_n =\sum_{k=1}^{n-1} {n - 1\choose k - 1} B_k A_{n-k},\ n>1 \] 递推复杂度 \(O(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

#define N 5007
#define mod 998244353

int fac[N], ifac[N];

inline int fpow(int x, int t = mod - 2) {
int res = 1;
for (; t; t >>= 1, x = 1ll * x * x % mod)
if (t & 1) res = 1ll * res * x % mod;
return res;
}

inline ll C(int n, int m) {
if (n < m) return 0;
return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

int b[N] = {0, 1}, a[N] = {0, 1};

int main() {
int n = rd();
fac[0] = ifac[0] = 1;
rep(i, 1, n) fac[i] = 1ll * fac[i - 1] * i % mod;
ifac[n] = fpow(fac[n]);
per(i, n - 1, 1) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
rep(i, 2, n) {
rep(j, 1, i - 1) b[i] = (b[i] + C(i - 1, j - 1) * b[j] % mod * a[i - j]) % mod;
a[i] = 2 * b[i] % mod;
}
printf("%d\n", (a[n] + mod - 2) % mod); // 去掉全红/蓝的情况
return 0;
}

整理系数之后就可以分治 NTT 计算了。复杂度 \(O(n\log ^2 n)\)